MySQL delete multiple rows in one query conditions unique to each row

You were very close, you can use this:

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

Please see this fiddle.