Qualquer solução que tente excluir tantos dados em uma transação sobrecarregará o segmento de rollback e causará muitos problemas de desempenho.
Uma boa ferramenta para ajudar é pt-archiver . Ele executa operações incrementais em lotes de linhas de tamanho moderado, com a maior eficiência possível.
pt-archiver pode copiar, mover ou excluir linhas dependendo das opções. A documentação inclui um exemplo de exclusão de linhas órfãs, que é exatamente o seu cenário:
pt-archiver --source h=host,D=db,t=VALUE --purge \
--where 'NOT EXISTS(SELECT * FROM `KEY` WHERE key_id=`VALUE`.key_id)' \
--limit 1000 --commit-each
Executar isso levará muito mais tempo para excluir os dados, mas não usará muitos recursos e sem interromper o serviço em seu banco de dados existente. Eu o usei com sucesso para limpar centenas de milhões de linhas de dados desatualizados.
pt-archiver faz parte do Percona Toolkit for MySQL
, um conjunto gratuito (GPL) de scripts que auxiliam em tarefas comuns com MySQL e bancos de dados compatíveis. 
