How to resynchronize replica in Postgresql
Since you deleted from pg_xlog, not from the archive, your first concern should be that you might lose the master, not just the replica.  

Cross your fingers, and immediately perform a checkpoint on the master.

If you get into the situation again where the archive process can't keep up and is threatening to fill up all space on the pg_xlog partition, rather than manually deleting from pg_xlog you should instead change archive_command to 'true'.  (Or change it to copy to somewhere else which is faster than its current setting is, but still preserves the files.  Make sure to then manually copy those files to their final, slow, destination once the emergency is over.)

As for saving the replica, please answer my other two questions, preferably by editing the question to incorporate that information.