If you are deleting 5,000 rows at a time, also consider the possibility that the DBMS may be laboriously updating the indexes for each row! Some DBMSes will do that; others are smarter.
What will consistently work, if you can do it, is to drop or turn-off the indexes on the table, then do the mass delete, then turn the indexes back on again. (When building an index in toto, DBMSes can use sorting and other algorithms that don't apply to individual changes to the index.)
Another "trick," again if you can do it, is to perform the delete as a series of transactions, say each one deleting only 500 rows. What you're trying to do here is to stay comfortably within the readily-available memory buffers that the server's likely to have without "straining," and also to keep the transaction rollback requirements small. In other words, you're changing your algorithm to keep the queries "friendlier."
If you actually plot the performance of a delete-query as the number of rows increases, you'll usually see a "knee shaped" performance-curve: up to a certain size the increase is linear, but then the line bends much more sharply upward, "hitting the wall." This is an informal test of course -- many factors can influence the behavior of a particular query -- but it's worth experimenting to see if this proves to be true in your case. (This kind of "hitting the wall" performance effect is commonly seen in a variety of situations when resources become tight, e.g. "thrashing" in a virtual-memory subsystem.)