In The Darkangel by Merideth Ann Pierce, Aeriel is an orphaned slave. One day she accompanies her mistress (and friend) on a slightly dangerous task, and the latter is abducted by a horrid creature called the darkangel. Aeriel returns (stupidly, or perhaps bravely) to attempt vengeance, but gets abducted herself, now to be slave to the darkangel and his many “wives” who are now just apparitions. She is helped by a dwarf (a common companion to Girls Underground) who lives in the labyrinthine caverns beneath the darkangel’s castle. When the dwarf sends her on a dangerous mission on hopes of killing the darkangel, she is also befriended by a majestic beast. Along the way, she must solve the meaning of an old rhyme, and return with a magic talisman before the darkangel takes his final wife and becomes completely evil.
SPOILERS In the end, Aeriel does not kill him, but rather finds a way to return him to his former, benign state. This makes the book one of the few who have what I consider a “happy ending,” where the girl stays with her adversary. Together, they must go on new adventures, and I believe the next book in the series has her confronting the darkangel’s “mother” – an evil witch-queen (in other words, the other type of GU adversary).