Ta bort miljontals rader i MySQL

DELETE FROM `table`
WHERE (whatever criteria)
ORDER BY `id`
LIMIT 1000

Tvätta, skölj, upprepa tills noll rader påverkas. Kanske i ett manus som sover en sekund eller tre mellan iterationerna.