How are fiction books such as novels sorted on the shelves at Japanese bookshops? Kana order seems to play a small part but not the whole part.
(I'm not asking about nonfiction books since those are ordered by category and are much easier to find)
From what I've observed, it varies from shop to shop:
Also, 文庫 and 新書 are placed in separate bookshelves on their own.
As for libraries, most of them follow the NDC classification system. NDC stands for Nippon Decimal Classification.
If you go to a library, you'll see that books are labelled with NDC classification number (分類番号 [ぶんるいばんごう]), a letter or two denoting the Kana to be used for further ordering1 (図書記号 [としょきごう] / 著者記号 [ちょしゃきごう]) and an optional series number (巻冊記号 [かんさつきごう]). These numbers are called 請求記号 [せいきゅうきごう] as a set and is used for ordering books and tracking down a book to a specific location in the library2 3:
Here's how it looks like (notice the small white labels at the bottom of the spine):
For fiction books, they fall under the main class of 9, and further classified like:
Again, 文庫 and 新書 will be in separate bookshelves in libraries too, and can be ordered by library → by series number instead of NDC.
 Usually the first letter of the primary author's surname, or the book title when there are a lot of authors.
I haven't been to a Japanese library yet, but judging from the book shops I have been to so far, fiction and such have been sorted by publishing house (such as Kadokawa or DC Comics).