I know it's in the ocean, and off the coast of an uncharted island, but I'm not sure where the island is. I'd been thinking it was Antarctica but I recently realized I was confusing it with At the Mountains of Madness.
From the Wikipedia article on R'lyeh:
- Lovecraft claims R'lyeh is located at 47°9′S 126°43′W. [H.P Lovecraft, "The Call of Cthulhu" (1928)]
- Writer August Derleth, a contemporary correspondent of Lovecraft and co-creator of the Cthulhu Mythos, placed R'lyeh at 49°51′S 128°34′W. [Derleth, A. The Black Island (1952)]
The latter coordinates place the city approximately 5,100 nautical miles (9,400 km) from the actual island of Pohnpei (Ponape), the location of the fictional "Ponape Scripture". Both locations are close to the Pacific pole of inaccessibility (48°52.6′S 123°23.6′W), a point in the ocean farthest from any land mass.
Lovecraft gives us the precise location:
Then, driven ahead by curiosity in their captured yacht under Johansen's command, the men sight a great stone pillar sticking out of the sea, and in S. Latitude 47°9', W. Longitude l23°43', come upon a coastline of mingled mud, ooze, and weedy Cyclopean masonry which can be nothing less than the tangible substance of earth's supreme terror - the nightmare corpse-city of R'lyeh [...]
I wonder what Google Maps shows there... :P
Source: the full story available online.