For the record, I have never seen this in our on-premise 6.11 system, and early on I did quite a bit of deleting whole pages of documents at once. I don't recall ever needing to do halves at a time.
Just a long shot, but is there a way to turn off the result list auto-refresh at some level? If one could temporarily turn that off, it could help. Alternately, do you know if viewing documetns in folders has the same issue? Folders can show up to 10,000 documents at once, all in one list, so if you can create a folder with a filter to display the documents you want, perhaps that would be an easier way to delete them? Just be sure you have the exact document you want!