A way to search by genre would be cool, then again that would bring up thousand s of results anyway. So at that point you would need more filtering in place (genre, region, age rating) to bring up any relevant search results. sounds like far too much trouble, maybe not.
How about this, here's the scenario :
I've clicked on the Browse page, scrolled down to Sega Genesis / MegaDrive, I've clicked on Megadrive (EU) and the list comes up.
Page 1 - 688 Attack Sub, AAAHH!! Real monsters, Adamms Family Values, etc.
Pretty simple numeric order through to alphabetical order, but I remember a friend playing a sweet looking shoot 'em up ages ago, but I can't remember the name of it.
I could use a list filter towards the top of the page (maybe above the page number select) to show shoot 'em up only. Ah there it is, I recognise it now, it was 'Gunstar Heroes'. Tick > Add to Wish List.
Pretty similar to what you said Olly, I suppose. Anyway, just a suggestion