Well, there is the Velvet Elivis Painting in the crashed UFO random encounter from the old Fallouts...
(Though I'm not going to dissolve yet another thread into meaningless debate over whether that was "canon" or not...)
The way I see the whole timeline split is that anything that happened after the split exists in a sort of probabilty bubble until it's mentioned one way or another in-game. (Sort of a Schroedinger's Cat-Box for videogame theory... an if a tree falls in the woods and no-one's there to here it sort of thing....) Sure there seems to be a prominent 50's theme to the surviving music you come across in Fallout. But whether that's because it underwent a rebirth of interest right before the War or whatever is largely up to interpretation. The game has made no mention of it either way.
So yeah - if they put Elvis songs into the game, then he existed and rose to popularity in the Fallout Universe. If he's not in the New Vegas game, it only means just that. There's still no in-game lore that would point one way or another.
And yeah - I think it would be very fitting to stroll into a ruined Las Vegas while listening to "Viva Las Vegas" over the radio...