It seems impossible on the iPhone itself. But if it is synced with iCloud, then log in to iCloud.com, go into Contacts, select all the contacts you want to delete, then click the lower left settings button and choose delete (or just press delete on your keyboard). If the contacts are synced elsewhere, like on Gmail, then delete from there. This is the only way I know to delete many contacts at the same time.