The lack of service was also partly blamed on people using mobile apps to redial the Centrelink number repeatedly.
The DHS says it has asked Telstra to find out how many of the 42 million were users attempting to call Centrelink.
In the period from June 2015 to April 2016, there were 29 million calls that received an engaged signal and for the previous 12 months the figure was 22 million.
"The analysis we've asked our provider to do is to strip out those that try less than a number of times per segment of time, because obviously it's reasonable for them within a minute or two to try again, but it's actually not reasonable for them to try a thousand times a day, you know," chief information officer Gary Sterrenberg told the panel.
DHS boss Kathryn Campbell said that a private call centre would be asked to provide 250 operators to cut down on the number of such calls.
But the union that covers Centrelink, the CPSU, said this number was small compared to the 1180 jobs that are proposed to be axed by the DHS.