MySQL master master replication, safe to delete rows on both masters?
Your question already has the key to your answer. It does depend on row based or statement based replication.
STATEMENT-BASED REPLICATION
If you run DELETE FROM tblname WHERE blahblahblah; and the rows matching blahblahblah do not exist, no big deal. Replication will just carry on. It will  just take you a lot longer to realize your data draft on the Slave (or in your case, either Master) if there were slight differences at all.
ROW-BASED REPLICATION
If you run DELETE FROM tblname WHERE blahblahblah; and the rows matching blahblahblah do not exist, that can break replication because the exact row info is embedded in the relay logs on slave. That row is expected to exist for the delete to happen. There is an error code for it:
sh-4.1# perror 1032
MySQL error code 1032 (ER_KEY_NOT_FOUND): Can't find record in '%-.192s'

You will likely see error log messages like these:

2014-02-27 22:03:00 4070 [ERROR] Slave SQL: Could not execute Update_rows event on table mydb.mytable; Can't find record in 'mytable', Error_code: 1032; handler error HA_ERR_KEY_NOT_FOUND; the event's master log mysql-bin.000166, end_log_pos 93114177, Error_code: 1032
2014-03-17 10:50:15 11596 [ERROR] Slave SQL: Could not execute Delete_rows event on table mydb.mytable; Can't find record in 'mytable', Error_code: 1032; handler error HA_ERR_KEY_NOT_FOUND; the event's master log mysql-bin.000337, end_log_pos 427881, Error_code: 1032

Here are other links that discuss this

Some MySQL slave errors?
MySQL Forums : Replication stops with Error 1032
MySQL Forums : Error 1032 - Can't find record in table
Bug #44873 : Replication failure error code:1032

For more insights, please read Advantages and Disadvantages of Statement-Based and Row-Based Replication from the MySQL Documentation.