First, I want to strongly endorse tim B's answer, I'm going to assume you read it already for mine.
You asked specifically about mythology. Mythology expands off of our innate fears and concerns, so while identifying those concerns is important that is not the final step to developing a mythology. Let me add some other fears or concerns, much like tim mentioned, which I feel could be an important enough factor to drive a mythology. This is all flow of thought, so forgive me if not perfectly written:
Movement. Most fish 'breath' by pushing water past their gills, meaning they must stay in constant motion or suffocate. This can result in a very deeply ingrained need to stay moving at all times. They may associate not moving with death the way we associate darkness (which for us meant predators with better senses about to eat us) with death. They may have euphemisms like "stopped swimming" for death, and "keep on swimming" may be the way the refer to someone who is struggling with something and is just trying to keep from losing control. This would also suggest being kept confined in small places would make them claustrophobic, since the limited ability to swim would be equivalent to taking shallow breaths.
As a culture and religion this could translate to a species that puts extra focus on continuing to stay busy and never stopping or giving up. Laziness, and specifically lethargic movement, may be a trait they associate with their villains and other 'bad' people.
Alternatively perhaps this species is more like dolphins, breathing with lungs instead of gills; which would explain how they can manage in 'air' like you said in your original question. In this case there is less of a focus on movement, however, know where 'up' is, and how far away it is, would be important to finding air. They would likely be far more comfortable with light above them then below them. Even if a room is fully lit, if the light isn't seeming to come from above they may feel uneasy or uncomfortable. They would likely fear darkness even more then we do, since darkness not only means predators but also that oxygen is too far away to breath. They would likely associate 'up' with good and 'down' with bad, as we do, but to an even more extreme degree. "doesn't know up from down" may be a horrible insult of someones intellect or even ability to survive on their own.
Lung power would likely be important for such a species. "check out the lungs on that guy" or "I swear he could go a day between breaths" may be tremendous complements. Their very psychology would likely be tied to their lungs and breaths, if they go long enough between breaths they may grow anxious, afraid, and desperate to move (up), as an adaptation to press those who needed a breath to move towards the surface. Availability of oxygen/air to breath would be a major thought of theirs, dying through lack of oxygen would be a major culture fear. I imagine their boggy men would be creatures that steal their breath or trap them away from air. "took his last breath" may be their euphemism for dying as well. Their super heroes and mythological creatures may be being who can go a long time or forever without breathing.
Reproduction: Most water based creatures reproduce via external fertilisation, it's simply an easier approach to evolve. However, external reproduction usually means a system with lots of eggs and a quick spray-and-go approach; in other words a R species. This would have a massive change to their psychology, I already discussed some of the psychological impacts of R vs K reproduction strategies in many other posts of mine. However, it's unlikely for an R species to reach sapience, so they probably won't be using that approach. It's probably best to create a species that uses 'standard' internal fertilisation and has only a few young, as it's a major challenge to create a believable intelligent R strategy species. How they reproduce in general could have a MAJOR factor on their culture and mythos, I would say reproduction is one of the biggest parts of our own early mythologies; but without knowing what avenue of reproduction you choose to go with I can't really go much into how it effects their mythos.
Closely related is their sense of beauty. They will likely be focused on sleekness and being aquadynamic, as travelling through water quickly and energy efficiently is a big deal for all aquatic creatures. Speed of movement may also big a big source of attraction to them, analogous to strength as the biggest physical trait humans look for in mates. Their mythical heroes will be sleek and absurdly fast, able to cover large distances quickly. Ability to control their movement in water, change directions quickly, move in all 6 directions, and not get disoriented by many direction changes, would likely be valued heavily as well, how much depends on how they feed and rather speed or finesse is a larger part of catching their prey (or not being caught by bigger fish). Like speed mobility and ability to change directions quickly would be prized in their hero. Physical deformities that lower movement speed or mobility would be considered the worst-they are bad for humans, but we have a particular disgust of non-symmetry that we value as heavily that likely will not be as relevant to aquatic species.
water quality would be a huge focus to them. The quality of water and contents of the water would significantly affect them in so many ways that it will be an all-encompassing focus of their mythos. They need to worry about light, but also how murky the water is (both due to viability and because murkiness may suggest contaminants that could harm them). If they have gills the quantity of air in the water will be something they intuitively sense, and less air in the water will always make them uneasy (and anxious to move more as with point 1). The currents of water will affect their movement. Water also is a much better conductor of heat meaning aquatic species will be far more dependent on water temperature since they will be less capable their internal body temperature, even technology like clothing will do less, thus the temperature of the water will be far more important to them then the air temperature is to us. They also care about water quality because it effects how much prey their likely find.
We have to worry about many of the factors above as well, but in our case each of them are seen as separate factors. The presence of light, air, disease, and food all depend on the quality of water to them; where as we see all of those as mostly separate, if sometimes related, factors. They will thus have a heavy focus on water quality in all their myths.
They will have adjectives to describe feelings and situations based off of water quality. Something feeling 'murky' to them will mean dangerous, uncertain, and hard to survive, as murky water limit ability to find prey but also a more general fear of murkiness being from contaminants that could be dangerous. Their version of Hell will likely be water filled with so much murk and other containment that they can barely see, which clogs their gills, or sticks on their sleek body to slow them and make it hard to move. In other wards an oil spill is their hell (insert BP joke here)
They may associate oxygen level with happiness. telling someone to have a oxygen rich water day may be the equivalent of saying they have a happy day. All the places we would use presence of light or darkness to describe a place as happy or sad they would instead use the degree of oxygen in water to describe the same connotations; assuming they use gills of course.
Figure water, and its quality, will be a huge factor in all their myths. Pure clear waters will be the perfect place they look for. If they are predatory then the presence of lots of fish will be important too.
Magics associated with changing the quality of water around them will likely play a key role in myth. With water being an all-encompassing factor of their life the ability to change it will be huge. Any place with have magic healing or blighting a place in our world it would take the form of changing the water quality in their myths.
Water currents. Closely related to the above, the flow and ebb of water currents would likely play a key role in culture and myths. While we have an awareness of the breeze in the air, and even of storms 'blowing in' we are far less aware of the natural flow of air around us; as it plays a less direct effect on our daily life. Water, however, will bring with its tides fish, pollutants, air, new 'smells', pretty much everything. As water quality is an all encompassing factor of their life tides which can change that water quality would be significant.
Tides would be associated with change, for better or worse, in their myths. Their terminology would likely replace 'omen' with tides. They may talk of an ill tide flowing in, or wish someone good tides.
Notice that they can not keep the water from changing when a tide comes in, so if they wish to stay in one area (rather then traveling with the tides) they will be far more dependent on the tides and what they bring then humans are. We have to worry about the wind bringing storms sure, but those are passing things; we mostly can control our environment more (I'll add another bullet point on this probably).
This means that their myths would likely reflect their concerns about the tides changing things, possibly even their inability to affect the tides. In some ways they may see the tides as 'fate'. If someone asks why someone never did something they had wanted they may wistfully say "it wasn't in the tides for me"
This would suggest one mythical being/god may be a god of the tides, who is roughly equivalent as the god of fate. He brings good tides to the worthy, and bad tides to the bad. Perhaps he is seen to manipulate people (or other gods) the same way as the tides, by pushing them towards his own goals subtle (remember, tides will generally be slower moving things, not like fast wind, so tides can still be seen as subtle even as they are life changing). In fact I would see a god of tides as likely being one of the greater gods of a pantheon, perhaps with elements of manipulator or trickster, less direct power as the other gods but subtle and far reaching strength by moving the tides that make him still one of the greater gods. The sort of god that pulls strings from the background to make everything happen the way he wants.
Going along with the tides, remember they are more complicated then our wind. With 6 dimensions, rather then four, to work with you can have tides pushing and pulling in more complex manners. For various sciencey reason tides would be more complex then the wind (that is close to earth and we experience) seems to be; and the depth one goes will likely play a key effect on the sort of tides you find. This may cause tides to be seen as not just powerful, but a complex and hard to be understood force. They may have 'wise men' who can read the tides, and being able to predict what subtle difference in the tides they will find could by seen as a mystical art. Tides could be associated with magic.
In fact magic would likely flow through the water current in many myths. Magic can be cast anywhere, but it propagates out on water the same way a drop of dye would spread out; as they are use to the idea of water spreading everything. Likely magical figures would radiate magic out from them through the water. The ability to 'read the tides' may be required to cast a spell at a distance, because magic users will cast their spell in a tide and wait for the water to carry the magic to the appropriate place. Diving deep (or high, if they live deeper down) to find the right tides may be a common concept in their myths; as it associates wisdom of reading tides with the unknown of swimming to a depth most of their kind is not comfortable in to double the air of unknown mysticism.
Senses: Humans relay quite heavily on our sight, but aquatic species won't be as dependent. Really most species are not as dependent on sight as us, we have evolved our sight to be better then the vast majority of species (especially non-flying ones) and have some of the most nuanced sense of color of any species out there; so it's unlikely any species, even non-aquatic, would have quite the focus on sight we do.
For aquatic species their sight would be dependent not just on time of day, but on depth from surface and murkiness of water, making dependency on sight potentially limiting. If they are a predatory species that eat fish their eyesight will likely be most developed towards sorting out movement of fish to be able to follow them as you chase them. In other words they would likely be better at distinguishing movement and quick changes, but not as good at looking at a still picture and appreciating nuisances out of it. If they hunt fish that live in groups their ability to not be confused by the groups motion, and instead focus on picking out a single fish from the school, would be a prized ability though.
They will likely have other senses that well developed, though how much depends on many factors of how they evolve and what their adapted for. Sound carries over much longer distances in water, but can also be distorted easier. The species would likely not try to use sound to pinpoint exact locations, but they would be evolved to pick up sounds from far away and be better at judging distance of sound and general direction. (note to self, add a communication bullet point below).
They would likely have a highly developed sense of taste/smell. I put those two together because the difference between the two is complicated. In a way our sense of smell is nothing more then 'tasting' the air, and the things carried in the air; with aquatic species these 'smells' can travel over further distances and be stronger, but the distinction between smelling them and tasting the water is kind of grey.
Similarly they may use this 'taste' of the water to describe things. As they are constantly 'drinking' water they are quite susceptible to pollutants in the water, and will likely have developed specific 'tastes' for a large multitude of potential pollutants, and they would subconsciously avoiding waters that 'taste' bad because that may mean that area is less healthy.
Perhaps a place has a 'bitter' taste, which suggests pestilent and wasting away (due to contaminants). Another area may 'taste' like blood, meaning immediate danger, or death. All the ways we could use smell to elicit an emotional response would apply here, but to a much larger degree, since the species would be more evolved to relay on their sense of taste/smell as much as their eyes to measure the world. The 'atmosphere' of most areas could likely be defined by describing in detail its exact taste, with different connotations to each of the many tastes. An area may taste 'wrong' if you want to build up a sense of foreboding, dread, or horror.
Communication. The species would likely use clicks like dolphins to communicate, which would spread out over a long area. The ability to stay in contact with people quite a ways away, even without seeing them, would likely play a role in their myths as well. I imagine many myths would have a 'voice' coming from the distance to speak to a certain dolphin, but one that he can not place or which has some unearthly or special sound to it to make it sound more holy/magic.
For instance, in their myths instead of God speaking to Moses via a burning bush moses-dolphin may instead simply hear a far off clicking without being able to see who it belonged to (which by itself may not be unusual or mystical to the species). However, the clicks may come to him directly, without sounding distorted or muffled the way sounds are under water, indicating they come from some holy source.
Clicks carry a little too well, making it harder to 'whisper' secrets, which is an interesting cultural impact in itself. Perhaps one of their diety-fishes is the fish of secrets, who has the magical ability to keep his clicks from spreading out to others to hear. This may make him seem a little evil or unnatural, having the ability to spread secrets without anyone being able to overhear as is natural. He could be an evil god, or just a trickster deity. Imagine if the fish of secrets was an extremely tiny minnow, small enough to be of little direct threat, but able to travel everywhere and watch everything, known for spying on everyone thanks to his small sizes. He then uses his secrets to talk to far more powerful beings, trading secrets for favors, but also tricking others. Relying not on massive power of most dietys, but his brains and knowledge and 'tricks' to survive despite being tiny and small.
size: the size of species in water varies drastically, far more then is possible on land (due to water better 'supporting' their weight aquatic species can reach gargantuan sizes compared to land based cousins). It's likely that our aquatic aliens, if sapient, would be on the larger end of the 'medium sized' fishes; basically dolphin sized (large enough to be strongly K selected, but small enough to still have short enough life cycles to allow evolution to work its magic). They will be use to the idea that the size of creatures around them can vary drastically. Whales that are massively larger then them, to fish smaller then the tiniest minnow. Their myths will likely reflect this idea of variable sizes.
Obviously, making a deity that is unfathomably huge is quite possible for these fishes, after all with blue whales already dwarfing your average dolphins it would seem that size is not a limiting factor, so why wouldn't there be deities of unbelievable sizes? it would seem more natural and easy to assume.
In fact, it's not unheard of to have gods or other powerful beings that held up the world, like Apollo. With aquatic species likely having some massive sized gods the concept of an Apollo-like god that is so huge he dwarfs the oceans seems a likely superstition. Perhaps their Apollo-fish is said to be huge and all the oceans are carried within his mouth? After all, the really big whales tend to have gigantic mouths, even relative to their size, and often eat very small fish in mass; so our aliens would be use to the idea that the biggest whales usually have tons of tiny fish in their mouth. It's a logical extension to assume that their largest deity is doing the same to them. I think it would be amusing if their version of ragnorak was the whale finally swallowing lol.
However, not all gods have to be larger then life. In our myths deities general are portrayed as huge, but that's because large size means lots of physical strength, which we respect; but which is not as important to aquatic species as speed. Plus, having a huge deity in our myth shows they are able to do something no mortal creature can, in aquatic worlds the fact that there seems to be no limit to the size of animals may very well make gigantic larger-then-life deities not feel as special; since it doesn't require godhood to be so huge.
Instead their gods will likely run the gambit of sizes, from Apollo-god to the minnow sized secrets-fish I mentioned above. They will likely have far more variety then our own gods. Since speed and dexterity would be valued more then direct might there is less of a need to make gods big to make then impressive; especially if the gods relied on magic or other mystical powers instead of overt strength. Likely the most common god size would be an alien just a little bigger then our aliens in size, but with sleeker build, being longer but not wider for instance; but this won't be as consistent across myths.
Magic which changes the size of creatures would likely show up a bit more in their myths then our own, owing to the fact that it seems plausible that huge gambits of sizes are possible, and that shrinking would not necessarily be seen as lessening someone, if they gained speed and dexterity to go along with it. Being able to shrink yourself at will would be a positive ability, and likely would be something a lesser god or demi-god would have as an ability.
In fact owing to the much wider range of aquatic species per cubic mile in oceans then on land animals on ground the idea of deities being able to take many varied forms will likely be a little more common, as will the idea of having shape-shifting deities.
the vast unknown: Our myths have always had stories about exploring far away places, but our ability to explore was often limited by physical ability to travel, mountains, deep forest, or rivers limiting our travel path. With oceans you can travel seemingly forever in any direction. Their myths would likely involve heroes who traveled unfathomably long distances to far off places.
However, in some ways this may remove some of the mystique of traveling so far. Creatures are more uniformly distributed. The same fish you see here your see 20 miles in any compass direction, because the environment will be the same (assuming the aliens don't live near the ground, where reefs and the like can add some more variance). On earth the changing environments of forest and mountain and marshes mean that very different animals can be found in environments that are pretty close together. Likewise when you finally manage to cross to a new area, you climb the mountain or use a boat to cross the river, your likely find different species, geographically cut off from those on the other side of the mountain and thus evolved a little different. All this encourages the idea that exploring new lands on earth will find new and different creatures. Our space-aliens may assume that the exact same fish will always exist no matter how far they travel in any compass direction because they never see a noticeable change if they keep swimming in a single compass direction.
However, there is still a way to get mystery, there are two new directions for fish to travel, up and down. The type of fish and species you find when traveling vertically through water changes quite quickly. In addition practical limitations will likely prevent most aliens from swimming too low, or high, from their preferred depth. Thus the extreme deep, and/or the extreme heights if they live in deeper waters, will offer an air of mystery (or should I say tide of mystery).
Thus if you want to show off how strong, or fast, or impressive your heroes and mythical creature are have them travel treat distances in the cardinal directions. However, if you want mystery, magic, adventure, or the unknown have them travel up or down. Most mystical things will reside above or below or aliens, not far away from them.
...Okay I could do more, but I think I made my point. I'm going to just stop now before I write a book.
