What I've called "pulp fantasy" grew out of the confluence of a number of literary antecedents, one of the most important of which was the Victorian adventure novel. These novels typically presented tales of derring-do against the backdrop of romanticized European colonialism, the degree of romanticization varying with the author -- some such novels were in fact subtle critiques or satires of contemporary geopolitics. Thus, they typically involve a "civilized" European (or American), often from a military or scientific background (or both), who ventures into "the wild" and encounters strange and wondrous things, including threats to his own civilization that he must overcome. Sound familiar?
Among the most influential of the adventure novel writers was Henry Rider Haggard, an Englishman who is generally credited, along Robert Louis Stevenson, of taking adventure novels to new heights of popularity and sophistication. His novels were among the favorites of later authors, such as Robert E. Howard, Edgar Rice Burroughs, Talbot Mundy, and Abraham Merritt, all of whom went on to be highly influential in their own rights. Consequently, Haggard is an important link in the chain of D&D's literary origins, one who's often overlooked or forgotten, because his novels are comparatively little read nowadays. His most famous novel is probably King Solomon's Mines, written in 1885, and whose protagonist, Allan Quatermain, is probably best known not through Haggard's own writings but through Alan Moore's The League of Extraordinary Gentlemen comics. Quatermain was likely a model for Indiana Jones and indeed is the archetypal Victorian adventurer.
Less well known is Haggard's 1894 novel, The People of the Mist, which the author calls in his dedication an "effort of primeval and troglodyte imagination" and a "record of barefaced and flagrant adventure." The novel focuses on a destitute English aristocrat named Leonard Outram. Outram begins the novel after having lost nearly everything important in his life, including his fiancée, whose social climbing father ends their engagement because of Outram's current circumstances. Embittered, Outram sets off to Africa to escape his ruined life and, perhaps, to find a new fortune. Once in Africa, he acquires a dwarf Zulu companion, called Otter, and rescues a young woman named Juanna, who was being sold into slavery. Outram and Juanna soon develop an affection for one another, but one fraught with quarrels and disagreements -- precisely the sort of tempestuous romance that later became commonplace in tales of this kind.
The People of the Mist are a legendarily wealthy lost race, whom Outram vows to discover so as to gain both fame and fortune. This he does -- how could he not? -- but soon gets more than he bargained for. The People are embroiled in a power struggle between those loyal to the monarch and those loyal to the priesthood of the crocodile god. As an outsider, his situation is both enviable and precarious, as each faction attempts to use him to their advantage. Outram and his companions soon find themselves caught up in danger after danger, escaping through sheer luck as often as their own ingenuity. Haggard does an excellent job of portraying the People's society, with much attention given to their religion. I have little doubt that this portrayal was widely influential; there are certainly echoes of it in Merritt and Burroughs in my opinion.
The People of the Mist is a surprisingly brisk read. Unlike a lot of 19th century novels, it's not slow or ponderous and even Haggard's many anthropological asides make for good fun rather than pedantry. His characters are also well drawn, although, as with reading anything much imitated later, there's often a feeling of déjà vu accompanying them. We have to remember, though, that Haggard's novels are the originators of so many of the tropes associated with pulp fiction, Saturday morning serials, and related entertainments. They're the fountainhead from which so much sprang. As I implied earlier, Haggard's novels do offer a romanticized view of European colonialism but they're not wholly uncritical and his portrayal of non-Europeans is more sympathetic and nuanced than one would probably expect. Otter, the four foot tall Zulu warrior, while clearly The Sidekick, isn't played for laughs, even though his character has a good sense of humor. The People themselves are also portrayed as more than mere cut-outs placed in the narrative to make Outram look heroic.
In short, The People of the Mist is fun and well worth a read. It's in the public domain, so it should be fairly easy to obtain online if you can't find a copy of it in printed form.