DELETE FROM `table`
WHERE (whatever criteria)
ORDER BY `id`
LIMIT 1000
Lave, enxágue, repita até zero linhas afetadas. Talvez em um script que durma por um segundo ou três entre as iterações.
DELETE FROM `table`
WHERE (whatever criteria)
ORDER BY `id`
LIMIT 1000
