Re: OK, I know why it happens, but still...
I find READ COMMITTED to be the "wrong" mode. But maybe you have good reason to use it. Or maybe this DELETE issue gives you a good reason not to use it.
InnoDB statements are not shipped to the slave until the COMMIT finishes on the Master. All the statements in the transaction (20K RBR rows in your case) are then suddenly shipped across the wire. And then, the slave starts executing them. Since replication is serial, it won't look at the next statement until it has finished your 20K deletes.
General rule (not just in your situation) -- Do not delete lots of rows all at once. 1000 might be a good chunk size. This means breaking up your transaction into multiple ones. If this is not acceptable to your ACID requirements, then you are caught between a rock and a hard place.
I recommend using a UNIQUE key (preferably the PRIMARY KEY) and doing it in chunks like
$leftoff = 0;
LOOP:
$cutoff = SELECT id FROM tbl WHERE ... LIMIT 1000,1;
BEGIN;
DELETE FROM tbl WHERE ... AND id > $leftoff AND id <= $cutoff;
COMMIT;
if RowsAffected == 0 exit loop;
$leftoff = $cutoff;
sleep 1 second
ENDLOOP
Notes
* The LIMIT efficiently bounds your scan for stuff to delete.
* The WHERE clause is in both statements.
* Only the DELETE needs to be in the transaction; if the $cutoff record gets deleted between the SELECT and the DELETE, the code still works.
* Because of other activity, you may not delete exactly 1000 rows each time. No harm done.
* The RowsAffected check only works if you are deleting consecutive rows. Otherwise, you need to walk thru the entire table (and use some other test for exiting)
* The sleep is to give some extra breathing room for the slave. (It is not needed for non-replicating systems.)
* For MyISAM, the BEGIN/COMMIT are omitted.