There is rarely any excuse for having a UI task that takes longer than a few seconds and doesn't have a progress indicator. That basically means that if you want to perform a 30 second task you should show that progress bar even if that now means it's a 60 second task.

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.