I’m not certain exactly what comes first, and what follows from what, though I suspect it varies from area to area.
What they seem to do is decide upon several familiar areas from the games, books, and previous iterations of WoW and decide they’re going to make an area from there. For instance, Outland is a mish-mash of Warcraft II and III Draenor (primarily Hellfire Peninsula, also see Netherstorm and Shadowmoon Valley for areas in the same feel) and areas from the books (Nagrand, especially Oshu’gan). New areas are then created to fill in the gaps, or provide variety to players who already feel acquainted with the terrain and want something new. Zangarmarsh is one of these, Un’Goro and Sholazar Basin fill the gap in the other iterations.
From there known locations are placed, sometimes a little off of their “traditional” locations for gameplay purposes (for instance, I think that the Razorfen instances are technically where Mulgore is in WCIII, but I can’t recall).
After that, a lot of the lead designers have spoken at BlizzCon about their design principles. From what I can gather just by searching for text (which is hard), it really is a LOT of level designers pounding stuff out. They have some basic things, like “choice and tradeoff,” and balancing between solo and group play. They also say they want to keep things that are familiar even among the most innovative content. The biggest thing that most summaries of the speeches say they expound on though is prototype and iteration. One summary says that one of them mentioned that he loathes design documents because even if everybody writing the document thinks it will be great, the actual implementation could fail pretty epically.
This means that primarily, among the level designers pounding out a lot of content, most of the content is essentially just thrown together (to be crude, obviously there is a lot of care and logic to it; especially in the story arena), but most of the content is thrown in and removed, gutted, changes, and polished to a mirror shine.
Because, outside of the original development of the game (which took a long time), the process is primarily done through content patches are very sparse major overhauls (expansions), they have a lot of time for their level designers and testers to refine the hell out of it. That is the blessing of not having to release content on a steady schedule outside of “the player base is getting too restless,” and especially the blessing of releasing it in chunks.
So yeah, their level design is run mainly by a lot of level designers and testers working a lot of hours, though the difficulty it is mitigated by large gulfs of time before any given content is “due.”