So I'm just going to be that guy and say, "The question is wrong."
You've explicitly disallowed religious texts from answers, but it means you'll never get the truth. In reality, the most well-documented, best-protected documents are those considered sacred by the people who wrote them. We will naturally see far more ancient documentation on religion and politics than anything else.
But just because something is part of a culture's mythology doesn't mean they believe it as fact. And things believed as fact aren't immune to being partially retold as fiction. The idea that modern sci-fi and fantasy writers didn't take many ideas from religion seems patently absurd to me.
Nat mentions in a comment,
... Paradise Lost was also a fictional work, but I've heard Christians cite it as actual religion. So where's the line? And if the line's original intention, then Dante's Inferno was clearly intended as fiction, yet it discusses alternate realms. Earlier works exploring the "underworld" were likely meant as fictions, too. Some argue that the Garden of Eden, from the start of the Bible, was also intended as allegory. I guess it just gets hard to tell what the original intention is once a work's old enough.
I would take it one step further and say that even if these original pieces were intended to be truth, there's no way other people haven't been creating deliberately fictional stories for just as long. Modern sci-fi is just the latest in a very long string of such stories stretching to before recorded history.
A note on Stack policies regarding religious beliefs and "sci-fi" or "fantasy".
To avoid turning the entire forum into a giant religious debate (and probably other reasons), there's a policy about not treating religious teachings or beliefs as fiction. But we're not treating these beliefs as either fact or fiction here. We're just noting that the concepts existed in some form.
If Odin came to Earth and gave the ancient Norse a physical tour of Valhalla, the concepts written about wouldn't be any more influential than if the entire story was invented around campfires over the centuries. This answer doesn't care one way or the other about the origin of the beliefs. Just that these beliefs were almost certainly the origin of many stories.
What is an alternate reality / parallel dimension, anyway?
Different people will, of course, differ in opinion on the exact definitions. But a simple definition of a parallel dimension is any physical location you can't access via normal travel through 3-space. Or 2-space if you're a Flatlander.
An alternate reality is any type of parallel universe that largely mirrors Earth (or the protagonist's homeworld if they're not from Earth) but has various shades of differences. Some of these are caused by branching timelines, such that normal Earth and alternate Earth were one and the same at some point in their shared past. Some are only superficially similar. Some invoke some type of shadow people, who not only mimic humans on Earth, but specific humans currently alive.
I doubt many ancient civilizations (if any) understood the concept of a separate 3-space reached by traveling ana or kata along a fourth spatial dimension. You could, of course, arbitrarily define parallel universes as requiring some such convention. But there are two problems with this.
First, not all dimension hopping is done via a fourth dimension. Narnia is reached through a wardrobe that makes no mention of dimensions. It's entirely possible for the wardrobe to connect directly between worlds without any external notion of direction. So you'd be arbitrarily defining many modern "parallel dimensions" as not being such.
Second, it completely misses the point of looking for a historical source of the trope if we only include highly pedantic definitions of the trope and act as if instances of the trope meeting these pedantic criteria were conceived in a vacuum.
What about the origin of "dimensions" themselves? (c. 1754)
The earliest example of the word "dimension" being used to refer to the modern mathematical concepts is from 17544 when Jean Baptiste le Rond d’Alembert wrote5
"I said earlier that it is impossible to conceive of more than three dimensions (italics of d'Alembert). A clever acquaintance of mine [un homme d'esprit de ma connaissance] believes that one might nevertheless consider timespan as a fourth dimension, and that the product of time with volume would in a certain manner be a product of four dimensions; this idea may be contested, but it has, it would seem to me, some merit, if only because of its novelty" [D'Alembert 1751-, Vol. IV, lOlO]."
Clearly, the idea existed before this article was published, but we have no way of knowing how long before.
What I'm having no luck finding is a source for the first time the mathematical concept of traveling through a higher dimension is published. Clearly, d'Alembert is only talking about representing time as a dimension, not as a means of travel to another world.
But I would say this puts a reasonably firm cap on the oldest material that could use this trope in its most pedantic form as being early to mid 1700s.
The Field of Reeds (the Egyptian afterlife, c. 2700 BC), the earliest recorded alternate reality / parallel dimension story I could find.
We can go back to ancient Egypt (c. 2700-1800 BC) and find mythology relating to an afterlife.1 2 The deceased's soul leaves its body then travels to the Hall of Truth, (hopefully) passing various tests before approaching the Lake of Flowers, where a ferryman, Hraf-hef, would take the soul to the Field of Reeds, a paradise version of home where things were better and nobody died.
This is about as close to an "alternate universe" as you can get without using the label. Sure, you have to die to get there, but it's a physical location that largely mirrors Earth that can't be reached by conventional travel.
Arabian Nights -- The Adventures of Bulukiya (c. 750 AD), the oldest fictional alternate reality / parallel dimension story I could find (not verified).
This answer comes from another question asking about the first record of explicit portals used to travel to another world.7
According to the other scifi.se answer, and Wikipedia8, the story has elements of portals, other worlds, oh my! But I read through the story itself9 and couldn't find anything along those lines. I scanned through the days after the story heading but saw nothing there either, except mentions of the afterlife and Allah having created our world and the worlds of Hell and Heaven.
This would beat my next contender, but only if it actually contains these plot elements.
One thing to note here, is that the author of Arabian Nights is clearly influenced by religious mythology, and consistently writes from a pro-religion perspective. Whenever he mentions Allah or Muhammad, he interjects some type of reverent comment to ensure nobody believes those are just characters in a story.
‘O my mother, I have found, in one of my father’s treasuries, a book containing a description of Mohammed (whom Allah bless and keep!)
in that island he saw serpents as big as camels and palm trees, which repeated the names of Allah (be He extolled and exalted!) and blessed Mohammed (whom the Lord assain and save!)
Even if it's not dimension-hopping, it's clear evidence of old fiction directly including religious mythology into the fiction's mythology without treating the religion itself as fiction.
The Divine Comedy (c. 1321 AD), the first alternate reality / parallel dimension (probably) fictional story I can verify.
In The Divine Comedy3, the protagonist (and author), Dante Alighieri starts on Earth, travels through Hell, and ends up in Heaven.
The descent into Hell could be literal enough. The Earth is rather large and could potentially contain a vast chasm underneath.
But Heaven is reached by ascending from the Mount of Purgatory (an island in the ocean) after emerging from the bowels of Hell. And it's described as copies of our solar system, with Earth, Mars, the Moon, etc. being present along with several mythological constructs such as the Empyrean.
Again, this very snugly fits into the definition of not only a parallel dimension, but an alternate reality. It's a place that exists alongside ours, only accessible via some portal to Hell, and has a close resemblance to our Earth.
Note that there is some contention that The Divine Comedy was believed by the author to be some kind of spiritual journey, and might fall under the banner of "religious belief". However, most people would consider it a work of fiction, and it was labeled such officially by the Catholic Church of the era.6
1 Egyptian Book of the Dead from the Ancient History Encyclopedia
2 Egyptian Afterlife - The Field of Reeds from the Ancient History Encyclopedia
3 The Divine Comedy from Cummings Study Guides.
4 Four-dimensional Space article on Wikipedia.
5 d'Alembert and the Fourth Dimension by Rosine G. Van Oss via Science Direct.
6 Quora Forum Post by Sonia Fanucchi.
7 What is the first instance of a portal to another world?, answer by OrangeDog.
8 One Thousand and One Nights article on Wikipedia.
9 The Adventures of Bulukiya from the Adelaide ebooks collection. Note that it's a small part of a large page which the link should take you to.