Изтриване на милиони редове в MySQL

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

Измийте, изплакнете, повторете, докато не бъдат засегнати нула редове. Може би в скрипт, който заспива за секунда или три между повторенията.