I've never had to work with that many graphic elements before so these are all untested ideas...
Are you deleting the elements by looping through the graphics container and calling the Reset method after each delete? If so, it's the call to Reset that is most likely slowing it down. Instead of deleting the elements within the loop, add them to a collection (and remove the call to Reset). Then loop through the collection and call DeleteElement.
You might consider creating features on a feature layer instead of graphic elements. You'd then be able to delete via query by calling ITable.DeleteSearchedRows, which will be about as fast as you're going to get using ArcObjects.
You might also try creating an FdoGraphicsLayer for the elements. According to the documentation, the FdoGraphicsLayer class also implements ITable, so you should be able to call DeleteSearchedRows on it. I'm not sure exactly how the query would look since a graphic element doesn't have attributes like a feature does. I've never done anything like this so you may find out that a lot of the methods on the interfaces the graphics layer implements are just not implemented. It would be some interesting R&D though.