Yes, you can clear the search.
First, in the search bar click the "X" to clear the text.
Then you'll see a blue "book" icon at the right side of the search bar, click it.
It opens up an interface that has "Bookmarks / Recents / Contacts".
For "Recents" just click 'clear' and confirm 'Clear all recents'
For "Bookmarks" click 'edit' to remove them.
Click on Maps in the top right hand corner next to the test bar their is a icon that looks like a open book. Click it once there you will see three choices on the bottom, Bookmarks, Recents, and Contacts. Click on Recents. You will see all your searches press clear. This will clear all searches.
I just wanted to THANK YOU for this post! I'm new to the whole iPhone 5 and when I could not delete the info, I called Apple Tech Support. The tech support rep put in a route on her phone and put me on hold. While I was on hold, I did a search and this forum came up. I followed the directions while on hold and all is clear! The tech support rep came back and said it could not be cleared. I did not have the heart to tell her...