Have yout tried the schedule job as well? I would also try to have a look in the log for answers. But having that amount of data in the wastebasket could be troublesome. I have had a similar experience with removing versions from pages when you have thousend of them. The solution for us was to create a sqlscript running on the actual db.
Might be a timeout or something since you have so many items.
The scheduled job only deletes pages that have been in the bin for 30 days.
Had a similar problem in a project once (where we had 20K pages in recycle bin). And we had to use sql directly against the db.
There's even a FAQ for the subject (even if it's a bit dated now) - See http://world.episerver.com/FAQ/Items/Recycle-bin-issues/
I have over 33,000 items in my recycle bin and when I try to empty the bin I get the following error:
Empty Recycle Bin
editSavePageVersionData: The WorkPageId dosen´t exist (WorkPageID=0)
June 26, 2:07 PM
June 26, 2:27 PM
Job Failed
Is this something that you can suggest why this is happening.
Jon