This is a problem inherent in WP and MySQL. When searching WP does a LIKE on all the post titles and post content. It’s probably the search on the content that is really slowing things down. I did find this article on searching by title only http://stackoverflow.com/questions/9468804/make-wordpress-search-only-in-post-title
