When you click the “…taking too long…” button, what error message do you get?
It may be too much for your server to handle cleaning 5,000 files in you pass. Does it clean some of them before the error message? You may be able to clean them in batches until there are few enough to handle without causing the error.
When I am cleaning a site that is as infested as yours is, I employee a technique that I call “Clean as you go”. It works like this: I start a Complete Scan and I watch the results as it progresses. Every time it finds about 100 or so infections I click the “Automatic Fix” button, but I don’t stop the scan, it still keeps going and finding more. This allows the popup results window to deal with the cleaning in smaller batches and by the time you are done scanning your final cleaning should only take a few seconds. Then you should run the Complete scan again to make sure you got them all.
Let me know how that works for you. If you still get an error message.