How to delete multiple contacts?
If they are Google contacts, I would probably sign into my account via a website and use the tools available there to select multiple contacts.
Yes, using a desktop webpage in Gmail ---> Contacts--->Manage is the fastest way and your phone contacts should update almost instantly if your data/wifi are enabled.