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 );