The monthly dev update letter is here and it contains a teaser for the upcoming add-on:
"Lastly, some of our adventurers have been venturing further afield than ever before, and are returning word of a ruined city to the south ... we sense there may be more there to explore ..."
It is pretty obvious that it is not Hyperborea, but previous tips are still applicable:
1. FC want to step back from eastern theme (Khitai and Turan),
2. The new zone is bordering with existing zones,
3. It's ancient, buried (??) and mysterious
4. Some Lovecraft tie-ins.
Lets look at the map, shall we? 
To the south we have Shem, Kush, Darfar and Keshan and all those have two things in common:
1. those are next to Stygia,
2. those have mysterious, ancient cities.
Here is what I have been able to figure out so far:
City of Kuthchemes
"He stood, the one atom of life amidst the colossal monuments of desolation and decay. Not even a vulture hung like a black dot in the vast blue vault of the sky that the sun glazed with its heat. On every hand rose the grim relics of another, forgotten age: huge broken pillars, thrusting up their jagged pinnacles into the sky; long wavering lines of crumbling walls; fallen cyclopean blocks of stone; shattered images, whose horrific features the corroding winds and dust storms had half erased. From horizon to horizon no sign of life: only the sheer breathtaking sweep of the naked desert, bisected by the wandering line of a long-dry river course; in the midst of that vastness the glimmering fangs of the ruins, the columns standing up like broken masts of sunken ships--all dominated by the towering ivory dome before which Shevatas stood trembling"
- REH, The Black Colosus
Why it might be the location: The city is indeed ancient and in pretty rough shape. When you look at the artwork you will notice that there is a lot of dust and decay being shown and the strong sun implies desert.
Why it might not be the location: the letter clearly states "our adventurers have been venturing further afield than ever before". Shem lies closer to the already explored areas because it is roughly between Aquilonia and Stygia. The story itself lacks the "Lovecraftian" beast, it is about sorcerer and how his skull met Conan's sword.
City of Xuchotl
"They were not looking into an open street or court as one would have expected. The opened gate, or door, gave directly into a long, broad hall which ran away and away until its vista grew indistinct in the distance. It was of heroic proportions, and the floor of a curious red stone, cut in square tiles, that seemed to smolder as if with the reflection of flames. The walls were of a shiny green material.
"Jade, or I'm a Shemite!" swore Conan.
"Not in such quantity!" protested Valeria.
"I've looted enough from the Khitan caravans to know what I'm talking about," he asserted. "That's jade!"
The vaulted ceiling was of lapis lazuli, adorned with clusters of great green stones that gleamed with a poisonous radiance."
- REH, the Red Nails
Why it might be the location: Pretty much nothing to support the claim that this is they city picked for new add-on expect that it is "further in the south".
Why it might not be the location:the city of Xuthal had very unique look for it's walls were made out of Jade and the whole city was covered by a single gigantic roof. The artwork clearly shows open space and no jade walls. Besides the way the story ends....lets just say the wouldn't be whole lot of NPC to talk to :D
City of Xuthal
"She murmured a faint assent and followed him so closely that she stepped on his heels, to his irritation. Dusk had fallen, filling the strange city with purple shadows. They entered the open doorway, and found themselves in a wide chamber, the walls of which were hung with velvet tapestries, worked in curious designs. Floor, walls and ceiling were of the green glassy stone, the walls decorated with gold frieze-work. Furs and satin cushions littered the floor. Several doorways let into other rooms. They passed through, and traversed several chambers, counterparts of the first. They saw no one, but the Cimmerian grunted suspiciously.
"Some one was here not long ago. This couch is still warm from contact with a human body. That silk cushion bears the imprint of some one's hips. Then there's a faint scent of perfume lingering in the air."
A weird unreal atmosphere hung over all. Traversing this dim silent palace was like an opium dream. Some of the chambers were unlighted, and these they avoided"
- REH, Slithering Shadow (Xuthal of the dusk)
Why it might be the location: The city has a lot of magic in it and the beast found it it's bowels is a CLASSIC creation lifted by REH from the works of Lovecraft. The city is located in the middle of the desert.
Why it might not be the location: The city is packed with luxurious items and decadent drug users, it is "alive" in it's own twisted way so hardly a mess that is shown in the artwork.
City of Alkmeenon
"Nevertheless he went warily, sword in hand, his restless eyes combing the shadows from side to side, his springy tread making no sound on the sward. All about him he saw signs of an ancient civilization; marble fountains, voiceless and crumbling, stood in circles of slender trees whose patterns were too symmetrical to have been a chance of nature. Forest growth and underbrush had invaded the evenly planned groves, but their outlines were still visible. Broad pavements ran away under the trees, broken, and with grass growing through the wide cracks. He glimpsed walls with ornamental copings, lattices of carven stone that might once have served as the walls of pleasure pavilions.
Ahead of him, through the trees, the domes gleamed and the bulk of the structure supporting them became more apparent as he advanced. Presently, pushing through a screen of vine-tangled branches, he came into a comparatively open space where the trees straggled, unencumbered by undergrowth, and saw before him the wide, pillared portico of the palace."
- REH, Jewels of Gwahlur
Why it might be the location: The city was ancient and in rough shape, but it was used from time to time by the priests who came to the city to seek the audience of a goddess. In the artwork there are clearly some torches so that implies the presence of humans. The story also have some Lovecraft tie-ins in a form of monsters dwelling under the city.
Why it might not be the location: The city is supposed to be enveloped by vegetation which is not shown in the artwork.
To sum it up:
Most likely localization: Shem and the city of Kuthchemes.
Second most likely localisation: Alkemeenon, Keshan.
Today I want to talk a bit about my love for the all things REH. I find that there are very few AOC players that in fact know things or two about Conan. Sadly most are as clueless as general population with their preconceived notions of skin clad, brainless barbarian brawler that drinks, fights and womanizes. While that is 
