The Kobo's library search actually works really well. Instead of using shelves I just search by author, title or series and find the book I want that way.
That said have you verified that your device is setup with all needed settings according to the Wiki post on Shelves/Collections?
https://wiki.mobileread.com/wiki/Kobo...nd_Collections