It's a creepy story! It's sword and sorcery! It's bogus pseudo-history! It's about a people who were driven underground, in an entirely literal way! It's about one man's quest in pursuit of a really bad idea! It's...
"
Worms of the Earth," by Robert E. Howard.
(...the worms crawl in and the worms crawl out, the worms play pinochle on your snout, be merry, my boys, be merry...)
I just listened to the HP Lovecraft Literary Podcast's episode on this story and was so impressed I had to read it immediately. My favorite part is the "witch-woman of Dagon-moor," Atla, the demihuman hybrid. She's angry and cunning and gets exactly what she wants. She's also lonely and bitter: no human men will have her, since she's part worm, whatever the worms really are. She manipulates Bran Mak Morn into going to bed with her, so that no matter how much of her life she spends alone, she can always pat herself on the back and say she had "the kisses of a king."
It's easy for me to go on liking her despite the fact that she railroads an unwilling person into sex. I expect this is partly because society leads us to laugh that sort of thing off when it's done by women, but it's also true that boy oh boy does it work well to establish her both as a villain and as a woman who has personal conflict and is kind of a hard-luck case. I told you I wanted more women villains, and Robert E. Howard delivers.
(Is she a villain? a monster quisling? a creepy mentor? the equivalent of Circe? depends who you ask.)
She just sounds cool-looking to an impartial observer: yellow eyes, many sharp little teeth, "mottled" skin, and a body that bends in unusual ways. She's also called the "were-woman"; I think that's Howard's vague way of indicating that she's not entirely human, but it sounds misleadingly as though she turns into a woman every full moon and spends the rest of the month as a man.
Warnings: gore, dubcon sex mostly offstage, racism/white supremacist ideas if you look hard.