Eliminazione di milioni di righe in MySQL

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

Lavare, sciacquare, ripetere fino a zero righe interessate. Forse in uno script che dorme per un secondo o tre tra le iterazioni.