I recently had to delete ~60k (spam) accounts, and I managed to almost double the deleting speed adding the following indexes;
The thread one is likely the most important one, this mostly impacts account renames and deletes
Code:
alter table xf_thread add index last_post_user_id (last_post_user_id);
alter table xf_report add index last_modified_user_id (last_modified_user_id);
alter table xf_warning add index warning_user_id (warning_user_id );
alter table xf_spam_cleaner_log add index applying_user_id (applying_user_id );
alter table xf_spam_cleaner_log add index user_id (user_id );