After finally reaching the fortress, you'll have to step out onto a ledge with a short green marble skull "fence" lining the outer edge. at the far side the "fence" meets a brown stone wall, with a small cave on its right side. However, along the wall on the left side of the "fence" is a narrow ledge leading around the cliff face to a cave with a berserk pack inside. Be careful not to fall back into the sea below.
Inside the main part of the fortress is a sprawling, roughly cross-shaped hall. There is a flat, marble landing in the center with a lava pool to the south (from which you entered the area), yellow-key-locked bars to the east, some windows and openings to narrower corridors to the north, and some stairs leading upwards to the west. There are rusty metal columns in each corner of the central landing. On the northern face of the southwestern column is a gargoyle face; shoot it to open a secret passage. Follow two short flights of stairs until you reach an outdoor ledge. Drop down onto the lower ledge to the right to get some rockets, then run across the gap to get the soul sphere.
From the central landing mentioned above, head westward up the first short flight of stairs, but not the second. There are small "towers" to the left and right, with lifts leading up inside them. Head into the left (southern) tower, and ride up to a short hallway culminating with a shallow alcove with a different texture than the surrounding walls. Open this rather obvious secret door to reveal a room with a teleporter that takes you to a tall tower outside the fortress.
After passing through the northern set of yellow-key-locked bars (the ones not near the yellow skull key itself) follow the stairs down and flip the gargoyle switch to gain access to a series of very cramped, maze-like corridors. At the start of the "maze", notice that the passage to your immediate left is blocked by a single metal bar. This passage leads to the secret area, but the bar needs to be removed first. Instead, head right, then left, and proceed straight through an archway and into a brown brick room. Continue going straight until you reach another archway on the left-hand side, and enter the room with the green torch. On a walkway up some stairs in this room is the switch that raises the aforementioned bar, granting access to the secret area. However, it's on a timer, so run quickly under the bar before it lowers again - it may take a few tries to find your way back in time. Ride the lift behind the bar up, and you'll see a soul sphere ahead of you. Run off the ledge you're standing on and grab it in mid-air.