You're not entirely clear whether you want to delete everything from the folder or just specific items, but this might help you.
If you want to delete everything in the folder, you could just delete the folder itself and create it again (Shift+Delete it though, or you'll have exactly the same problem with your Deleted Items folder).
If you only want to delete some items, you might get away with creating a new folder, moving items you want to keep into this new folder, delete the old folder (again Shift+Delete it) and then rename the new folder so it has the same name as the old one.
If you want to be a bit selective on what you delete, you could try and use Outlook in a bit of an unusual way. Create a new folder in the mailbox (e.g Stuff to delete) and then create an Outlook rule to move messages with your specified criteria to the Stuff to delete folder. Run the rule on the large folder and then Shift+Delete the Stuff to delete folder.
You'll need to bear in mind that if you do any of the above, Outlook might take forever to complete the action and appear as though it's hung/crashed - more than likely it hasn't and is just churning through the sheer volume of messages. Make yourself a cup of tea and give it a while, it should come back eventually.