Usually by the time your software knows fully all the things that need to be done, then you are almost done anyway.

One approach is to remember how long a similar task took, and present progress based on the expected time will be similar.