There has actually been a lot of research into how to make progress bars "feel" right -- it turns out that certain psychological tricks can help with that, too. Roughly speaking, it tends to be better to be conservative at the start (i.e. give a worst case estimate) and then improve it over time, than the other way around. Hence a simple trick to improve the user experience is to take whatever you think will be an accurate value for the progress, but then apply a scale to it to make it appear slower at the beginning, and faster at the end. This is studied and discussed in depth in the paper "Rethinking the Progress Bar": http://www.chrisharrison.net/projects/progressbars/ProgBarHarrison.pdf
For example, if x is the progress ranging from 0.0 to 1.0, then instead of using x directly, use f(x) = (x+(1-x)/2)^8 to calculate the progress estimate you are going to display to the user.
The key observation here is that if I am told something will be finished in 1 minute, but then it turns out to take 2 minutes, I am upset; if instead I am told it will take 2 minutes, but then it finishes already after 1 minute, I'll be happy. Of course this has limits, and one needs to strike a delicate balance: if the original estimate is too far off and bad, the negative reaction to the initial bad estimate and how far it is away from reality will create a strong negative reaction on its own (what would you think if you were regularly told "performing this operation will take ~2 days" when it ends up needing only 1 minute each time...)
There are other tricks to make the UI feel "faster" when it comes to progress bars, see e.g. http://uxmovement.com/buttons/how-to-make-progress-bars-feel-faster-to-users/