Now, there's no way I can get every classic of every genre that's influenced World of Warcraft into a list that would fit on this site. There are hundreds of potential books out there. So I'm just going to hit some highlights and let y'all go wild in the comments filling in the blanks.
J.R.R Tolkien's Lord of the Rings - Tolkien is the 10,000 lb gorilla in modern fantasy. If you're not influenced by him, you're a reaction to him. The reason there are multiple kinds of elves and dwarves running around Azeroth fighting orcs is because of Tolkien's impact on fantasy. If you want to get the tropes, you should probably read this.
Robert E. Howard's Conan and other stories - Howard is the other huge gorilla influencing modern fantasy. I mention Conan as his most famous creation, but there's just as much good stuff to be read by Howard that has nothing to do with the Cimmerian. His Solomon Kane, Kull, Bran Mak Morn, and his forays into horror and historical fiction all blazed from an imagination so incandescent that it burned the man himself out in a short amount of time. Be warned - most of this stuff was written for the pulps, and it has all the virtues and all the flaws of pulp fiction written in the 20's and 30's. It's often racist, sexist, and ranges wildly in quality.
Fritz Leiber's Fafhrd and the Grey Mouser series - Warcraft's bent for flawed characters with feet of clay even when they command armies or nations comes from Leiber's most famous creations, heroes who were much less engines of destruction than flawed, greedy, sometimes amoral men.
Marion Zimmer Bradley's Darkover series - Specifically the idea of Azeroth and Draenor as planets visited by people from other worlds. It's not unique to or invented by Bradley, but she did a lot to popularize it and was one of the first and most popular authors to do so.
Kathryn Kurtz's Deryni books - It's easy to forget how unusual Kurtz's approach to magic and fantasy was when these books first started coming out. Her approach to a pseudo-histroical fantasy setting can be felt in WoW's human kingdoms.
Glen Cook's Black Company series - This series is exactly how I think of my guild in terms of the WoW fictional setting. If you want to try and wrap your head around what a guild would even be, the Black Company is a really good model.
Michael Moorcock's Elric series - Honestly, the whole Eternal Champion cycle is worth reading, but Elric is the easiest character to start with. The sorcery level in the Moorcock books is a lot closer to WoW that most other heroic fantasy, with characters capable of wreaking untold devastation with magic. Also, Moorcock is just a hell of a writer.
John Gardner's Grendel - WoW has a lot of this book's DNA, with the idea of presenting what is usually seen as the monster as a sympathetic hero. If you play an orc or troll, this book is worth reading. Heck, it's worth reading anyway.
Jack Vance's The Dying Earth series - Vance's influence is primarily in how magic and spells work in WoW, and it's by inheritance. The Dying Earth itself also has some influence on places like Outland, a world on the brink of destruction, and there are other books in this vein such as Gene Wolfe's Book of the New Sun.
C.L. Moore's Jirel of Joiry stories - Some of the earliest fantasy fiction to have a female protagonist, and one who does her own adventuring, straps on armor and a sword and deals in wholesale violence. In her adventures Jirel fights wizards, demons, and strange cults of ghost eaters.
Mervyn Peake's Titus Alone - Really, the whole Gormenghast cycle, but Titus Alone really has all the weird retro-tech touches we recognize in WoW. Goblin and gnome engineers are rooted in the steampunk genre that works like this helped create. Also see Jack London's Goliah, the works of Jules Verne, and Gregory Keyes' Age of Unreason. Oh, and Paul Di Filippo's Steampunk trilogy, of course.
Howard Phillips Lovecraft's Cthulhu Mythos - The Old Gods of the Warcraft setting are lifted directly from Lovecraft. Lovecraft himself encouraged others to write in what came to be known as the 'Cthulhu Mythos' including Robert Bloch (writer of Psycho), Robert E. Howard, Clark Ashton Smith and many others. Lovecraft's esay Supernatural Horror in Literature is still a must read for an understanding of how horror works as a genre.
Dungeons and Dragons - I mentioned Vance earlier as an influence, and D&D is why. D&D is to video games and fantasy what Tolkien is to the entire genre - if you present a world with dragons, monsters, and magic for players to explore and murder stuff on, it's either going to be descended from D&D or a reaction against D&D, and the Warcraft setting manages sometimes to be both of those things. If you have never managed to play D&D or any pen and paper RPG, you probably should at least once to understand where things like character classes come from.
Jenny March's Penguin Book of Classical Myths, Robert Graves' The Greek Myths, Kevin Crossley-Hollans's The Norse Myths, Anne M. Birrel's Chinese Mythology: An Introduction, and World Mythology: The Illustrated Guide. These are all books I own, so I feel secure in recommending them for you to get a sense of the mythology that's being tapped for Titan lore in places like Uldaman, Uldum and Ulduar, as well as Mogushan Vaults and Throne of Thunder. While you're at it, Jack Kirby's Fourth World and Walter Simonson's run on Thor are useful for getting your head around the 'space cosmic gods' aspects of the Titans.
Okay, so that's my picks. (Leaving out books I love like The Worm Ouroboros, Jurgen, and The Once and Future King that I didn't really think fit) But the best thing about posting such a list is the comment section where you all chime in with your own ideas about what books people wanting to better grasp the Warcraft setting should be reading. So have at it, people.
Mists of Pandaria is here! The level cap has been raised to 90, many players have returned to Azeroth, and pet battles are taking the world by storm. Keep an eye out for all of the latest news, and check out our comprehensive guide to Mists of Pandaria for everything you'll ever need to know.