I'm assuming you didn't just murder Soego at random? Because that's supposed to be part of a quest Hargrimm gives you (depending on how it goes). Anyway, there are two ways to get out of the Dead Nations peacefully:
SPOILERS:
1. Get Hargrimm to trust you. This involves doing two tasks for him: killing some cranium rats and finding proof that Soego is a spy. The former is obvious, you just need to search for them. Killing Soego by itself is not a solution for the latter (in fact, Hargrimm explicitly prefers that you don't do this), you need to find proof of his activity. He keeps it somewhere close by, so this requires either killing him or somehow distracting him. His skull isn't relevant for this quest, although it can be used for another one later on.
2. If you have high Charisma (I think 16+, not entirely sure though, as I cast Friends for this conversation), then you can go the alternate route and charm Stale Mary into helping you. This requires learning to speak with dead, but since she is the one who teaches you in the first place, this isn't a problem.
I'm not sure if you can kill Hargrimm for the key, but considering he is a priest, you'll probably be dead from Call Lightning before you manage to do enough damage. :/
