This is what I did:

mysql> delete from user_table where username='john';
Query OK, 203601 rows affected (6 min 6.88 sec)

and the username column is indexed as well.

We have 63 columns in the table with 5 indexes. No, there are no large blobs in the table.