Les dejo la consulta que encontre y voy a utilizar.... gracias !!
Código PHP:
DELETE FROM atATDClienteTempMes USING atATDClienteTempMes,
atConciliacionParcial60Prueba WHERE atATDClienteTempMes.idATDCliente = atConciliacionParcial60Prueba.idATDCliente
pudo borrar los 600.000 registros en 12 min aprox, asi que es lo que estaba buscando
Esta consulta la encontre en el manual de MYSQL
http://dev.mysql.com/doc/refman/5.0/es/delete.html