My own favored interpretation of the Lady of Pain, despite all the blather above, is that she's the living spirit of Sigil and both she and it are remnants of a previous multiverse destroyed before the beginning of time, and she's always lived in her city and always will.
Or else she doesn't exist at all. She's a rumor and a hoax and there was never anything like her.
Shekinester is simply based off of Hindu mythology, where the gods usually have opposing (i.e. literally opposite) aspects. The most well known example of this is Vishnu the creator and Shiva the destroyer, both aspects of the same god.