Eliminando millones de filas en MySQL

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

Lavar, enjuagar, repetir hasta cero hileras afectadas. Tal vez en un script que duerme por un segundo o tres entre iteraciones.