How about having a button on the top or bottom bar that says "sorting"? When you click it, the song wheel moves off the screen to the right, and a sorting menu moves in in its place, and all the options can be there:
Sort by:
Title
-Show All
-#
-A
-B
-[...]
-Y
-Z
Artist
-Show All
-#
-A
-B
-[...]
-Y
-Z
Beatmap creator
-Show All
-#
-A
-B
-[...]
-Y
-Z
BPM
-Show All
-60-69
-70-79
-80-89
-[...]
-190-199
-200-209
-(etc)
Difficulty
-Easy
--1
--2
--3
--4
--5
-Normal
--1
--2
--3
--4
--5
-Hard
--1
--2
--3
--4
--5
-Insane
--1
--2
--3
--4
--5
Top 50(/25?) Most played
-Easy
-Normal
-Hard
-Insane
Own high score
-Easy
-Normal
-Hard
-Insane
Favorites
-Favorites list A
-Favorites list B
-Favorites list C
Add to Favorites
-Add to Favorites list A
-Add to Favorites list B
-Add to Favorites list C
-x means that it expands, like multiple difficulties expand for one song.
For the alphabetical and the bpm categories, only show those difficulties if there's a song that falls under it. So if you don't have a song that starts with Z, you wouldn't see an option to show all songs with Z (like Stepmania does).
Show All means it shows all the songs sorted by that criteria, while the specific options only show anything that falls under that option. This would make going through large songlists easier.
If double expanding menus isn't possible, then just change the difficulty section into 4 separate sections.