You can delete the entire "conversation" which deletes all messages contained in that conversation at once. Not sure if it will free up the space you're missing but it's much easier than going through message by message. Note that this will also delete any sent/received photos within the conversation as well so be sure to save what you need to your Camera Roll.
When you are in Messages, tap the Edit button, then select the conversation (the person who's texts you want to delete) by tapping the round selection bubble to the left of the conversation, then tap Delete at the bottom right.
A shortcut is to swipe the conversation to the left, then tap the Delete button that will be revealed.