I have iOS 9.2 and updated Music to the latest version. There is no "view all songs". But perhaps you found some way? Like I just want to see all songs, not playlists, not genres, everything. I'd love to find out :)
The reason you couldn't figure it out is because Apple has completely abandoned usability in favor of a comically flat UI aesthetic.
A UI disaster that most Music users will never discover.