In most of the articles and studies I've read about Robert E. Howard's reincarnation tales, stories about men who remember their past lives, Jack London's novel The Star Rover is usually pointed out as the most likely influence on Howard for writing these yarns. I believe this is the case for the most part, however I think there is one more additional source, H. Rider Haggard's novel, The Ancient Allan.
In this novel, Haggard's protagonist Allan Quatermain inhales the fumes of a plant called Taduki and this causes his spirit to return to a past life.
"Once, before we took our great homeward journey across the desert, Lady Ragnall and I had a curious conversation about this herb whereof the property is to cause the person who inhales the fumes to become clairvoyant, or to dream dreams, whichever may be the truth."
After inhaling the fumes, Quartermain lapses into a trance and begins to see himself as figures from different points in history. He sees himself as a spear wielding tribesman fighting another spear man to the death and then speaks of other past lives before settling down to the main plot.
A couple of years back, when Del Rey brought out a paperback of the Wandering Star Bran Mak Morn volume, a recently discovered REH novel fragment was included in the miscellanea in the back of the book. The untitled novel had been started sometime prior to 1923 and began thus:
"Men have had visions ere now. Men have dreamed dreams. Faint glimpses of other worlds and other ages have come to us, as though for a moment the veil of time had been rent and we had peered fearfully into the awful vistas."
The interesting part comes a few paragraphs later.
"But in my manhood the clearest sight was reached, in manhood when I purchased, for ten times its weight in gold, the Mystic Plant of the Orient."
"Taduka," I shall call it, though it is not Taduka, nor is it anything known to or by, white men. It is not an opiate, nor is its effect harmful in the least. It is meant to be smoked and when smoked the world of today fades from about me and I travel back into the ages or forward into the future."
Howard's protagonist follows this with descriptions of the different time periods he has visited, pausing for the occasional vignette as Haggard did. I think the Taduki/Taduka speaks pretty much for itself. Now as far as I know Howard never mentions Taduka again. Howard's most frequent time traveler, James Allison, is a crippled and disease stricken man who can remember his past lives for no apparent reason. The protagonists of The People of the Dark and The Children of the Night get bumped into past lives by blows to the head in the time honored tradition of Mark Twain's Connecticut Yankee. In The Thunder Rider, a modern day Comanche relives his past life through an Indian ceremony.
I did notice one other thing in the James Allison stories that might be an echo of Howard's reading of Haggard. Allsion is quick to remind the reader in two of the stories that when he is seeing his past lives he still remembers that he is James Allison. From The Valley of the Worm:
"Yet it is not alone with the mouth of Niord that I will speak. I am James Allison no less than I was Niord..."
And from the Garden of Fear:
"I must speak of what I saw, not alone as Hunwolf, but as James Allison as well."
And from the Ancient Allan:
"I, please remember always that I knew it was I, Allan, and no one else, that is, the same personality or whatever it may be which makes each man different from any other man, saw myself in a chariot drawn by two horses..."
A quick check over at Rehupa's Bookshelf feature, a vastly impressive alphabetical list of all the books that Howard was known to have owned, read, quoted, or spoken of, does include The Ancient Allan as one of three H. Rider Haggard books REH had read. The Ancient Allan was released in 1920, so plenty of time for it to be read and absorbed by the young Robert E. Howard before he began his attempt a a novel.