Okay but presumably it's doing something with that extra time, is it valuable?
This might be helpful if the filenames and sizes make you realize that you're trying to delete the wrong folder so that you can abort immediately. Other than that, it's just eye candy.
I'd probably try to cheat in this particular scenario either by keeping a best guess for the recursive delete complexity in the file system itself, or by simply showing a worse progress indicator such as a counter of files without a total count. The progress indication doesn't necessarily need to include time remaining, especially when the cost is this high.
Exactly. I don't particularly care which file out of half a million it's on -- I just want to know at a glance if it's still running or has somehow frozen/locked up.