MySQL elimina varias filas en una condición de consulta única para cada fila

Estuviste muy cerca, puedes usar esto:

DELETE FROM table WHERE (col1,col2) IN ((1,2),(3,4),(5,6))

Consulte este fiddle .