To delete your search history, learn about clearing activity saved in My Activity.
Just some random thoughts:
Try CTRL+H to go directly to your browser history. There are two (2) links titled History you need to click. It's a little confusing, at least to me. You should see this:
Then click "clear browsing history" on the upper left.
If that's not there, we have a whole 'nuther issue!