If asked to do so, I would generally classify him as "hard rock" (just better at it than most people). Extended songs are also a distinct minority of his catalogue, want to say they only show up on a couple albums. But whatever, arguing about labels. As a great man once said, "If you label me, you negate me." Doesn't make him more or less awesome for being filed somewhere else (although I would probably stop short of agreeing with your parenthetical).
Joe Satriani: Musterion
Speaking of, I apparently forgot I had this album. Professor Satchafunkilus and the Musterion of Rock. Yes.