Labyrinth Location
From UO Excelsior Wiki - Ultima Online Free Shard
The Labyrinth is reached via the Grimswind Ruins east of Luna in Malas.
The Coordinates are 114° 52'N, 61° 1'E
From here you must walk thru the northern most archway as shown here:
You will end up in a secluded area with mountain above you.
Head West-northwest to the entrance. The Coordinates for the entrance are 57° 7'N, 28° 45'E
The entrance looks like this: