There are apps that delete multiple contacts. Here's one. I don't know anything about this. There's other apps that do the same.
Multiple contacts delete by socioapps https://appsto.re/us/safgM.i
Settings > General > Reset > Erase All Content and Settings will get it done. But at a fairly steep price - it will totally wipe your device (including multiple contacts "all at once") and restore your device to factory settings.