Sletter millioner af rækker i MySQL

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

Vask, skyl, gentag indtil nul rækker påvirkes. Måske i et script, der sover et sekund eller tre mellem gentagelserne.