You should be able to just select each message in the list of messages and delete more than one at a time. Alternatively you can swipe left (or right, I forget) to delete.
Just touch the circle image left of the message. A check mark should appear. Do that for all message threads then hit the garbage can in the upper right.