Hi,
Yikes, that's definitely a very large number of items to delete at one time. When trying to delete them all at once, it's likely that DSpace is waiting for them *all* to succeed before saving the changes. That's why the timeout is occurring.
Once the Collection is smaller in size, a deletion from the UI should no longer timeout. I'm honestly not sure what size you'd need to get it down to though, as that's very dependent on your local setup, bandwidth, etc.
The only other batch deletion option I can think of would be to write a small script (in the programming language of your choice) and using the DSpace REST API ("DELETE /items/{item_id}"). But, that'd require first figuring out the list of Item IDs which you need to delete (either from querying the database or Solr, or similar).
https://wiki.lyrasis.org/display/DSDOC6x/REST+API#RESTAPI-Items
Hopefully that gives you some ideas to start with,
Tim