Suppression de millions de lignes dans MySQL

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

Lavez, rincez, répétez jusqu'à zéro rangées affectées. Peut-être dans un script qui dort une seconde ou trois entre les itérations.