This is actually how our search menu is supposed to work. That being said, let me explain how you can get the best functionality out of the search menu.
If you type in a word and do NOT tap the "Search" button on your keyboard, OnSong will only search through song titles beginning with that word as opposed to song titles with that word, song material containing that word, etc... This might be the issue that you are experiencing. But if you type in a word and then you do tap Search, OnSong will do a deeper search and find all the songs in your library pertaining to that word. In your case, you will likely just want to tap "Search," and OnSong will list all songs in your library that have the term you are typing in.
Essentially then, you can still search for songs the way you always have. All you need to do is tap Search (it should be a blue button on your onscreen keyboard) once you are done typing in your word, and Search will function just as it used to for you.