Older Than Feudalism: A special mention to Zeus/Jupiter in Greek and Roman mythology: not only is he an unfaithful god who seduces human women, he takes the appearance of various animals (swan, bull (!), a shower of gold, etc.) to do so.
The wife of the King of Minos mated with a sacrificial bull sent by the gods and gave birth to the minotaur. This was as punishment for Minos refusing to sacrifice it.
Centaurs love this trope, in both behavior and origins.
Satyrs constantly go after human and/or nymph women.
In many myths, demons are unable to breed naturally, and must instead mate with a human, producing a demonic offspring. Hence the Incubi, Succubi, and various other Horny Devils.
The Hippogriff, half-horse, half griffin. As griffins eat horses according to mythology, it was seen as a metaphor for a impossibly improbable thing, especially since the Hippogriff was never believed in, even at a time when griffins themselves were believed in.
To avoid paying for the construction of Asgard (by triggering a late completion clause), Loki turned intoa mare in heat so the builder's horse would run off. He gave birth to Sleipnir, the eight-legged horse of Odin, who carries the honored dead to Valhalla. Loki's other animal children include the great wolf Fenrir and the Midgard Serpent, destined to kill Odin and Thor respectively.
The Japanese seem to be most fond of this trope, which could explain why this regularly appears all the time in their popular culture.
It's quite common in East Asian culture in general for men in myths to end up marrying fox-spirits or ghosts. In one unusual case, a scholar in a Chinese folktale was visited in the night by the (human formed) spirit of a grasshopper, who he later saved from a spider.
Tragic romances between mortals and The Fair Folk, or Mer creatures, or similar beings are common in European folklore.
One Chief of the Macleod clan according to legend fell in love with a Fey. After twenty years she grew lonely for Fairy Land. She left him with a half-fey child. Later she heard the child crying and came back to lay a magic blanket on him. This magic blanket became the Fairy Flag that could give the Macleods fey-help three times when called upon (as might be expected, this was in Highlanders Favorite Sport). Photos of it were taken into battle by Macleods in World War II. As the allies won maybe the Wee Folk were doing their job right.
One version of this says that the Real Life flag was a standard Harald Hardrada had left with a friend of his in Scotland before going to his fate at Stamford Bridge. This story is interesting enough in its own right though not quite as much as the idea that it was a gift from a fey-lover. Whatever the orgin, the real Fairy Flag still hangs in the Macleods' ancestral castle; it is real enough even if fairies are not.
Some interpretations of Genesis 6:4, which reads- "The Nephilim were in the earth in those days, and also after that, when God's sons came in to men's daughters. They bore children to them. Those were the mighty men who were of old, men of renown." Some suggest the "sons of God" imply possibly fallen angels. Others suggest it refers to irresponsible attitude of the human leadership.
There are many famous Chinese myths and stories that involve Interspecies Romance. In fact they're probably more common than 'normal' human and human romance stories.
The story of Madam White Snake involves a snake spirit taking the form of a beautiful woman who then falls in love and marries a human man. The human man eventually betrays her to a priest (who is himself a toad spirit), but not before they have a human son. Madam White Snake is imprisoned beneath a tower, but her son grows up and finally manages to free her, and she ascends to heaven.
Another story tells of a poor scholar who nearly dies of starvation near a temple. In his dream he meet with a bunch of crow spirits who give him a special coat to be like them, and he is able to hunt with them for food, and eventually meets a nice female crow. When he wakes up, he thinks it was all a dream and the locals give him enough money to make the trip back home. Eventually he manages to pass his imperial examinations, and on the way back to his village he provides an offering to the temple and to the crows, asking for his crow-wife to remain if she was there. She later meets him and reveals she has ascended to the role of the guardian spirit of a nearby river, and he builds a home near the river. They also eventually have a son.
In Journey to the West, the Bull Demon King is married to Princess Iron Fan, who may or may not be a humanoid and sentient literal 'iron fan' (her name could refer to her weapon of choice). They have a son, the Red Boy.
One origin story/myth is that of Pan Hu, the Dog King/God. The story goes that there was a king who was fighting a war with another. He gave an offer to anyone who could bring the head of his rival, in exchange for the hand of his daughter. His personal pet dog heard this and managed to kill and retrieve the rival king's head. With no choice but to fulfill his promise, the king gave his daughter's hand in marriage to the dog. The dog took the princess into the mountains, and told her to wait for him as he meditated in a cave blocked by a boulder (in some tales, a giant bell) in order to attain human form. The princess however, became worried after several days with no food and water or communication from her dog-husband, and opened the cave/bell prematurely, leading to her husband having the body of a man but the head of a dog. In some tales, he never attained human form but always had sentience. The two would eventually produce many children, who would then form the various tribes that live in those mountains and trace their heritage back to Pan Hu.
It should be noted that in just all stories, the children of these pairings are always noted to be superior to normal human children - more intelligent, physically perfect, prodigies, magic abilities inherited from parents etc. Unlike many other religions, interspecies pairings were considered far more beneficial than stigmatizing.
The real life phenomenon "hybrid vigor" gives this an element of Fridge Logic.
Medieval bestiaries described the leopard as the result of a lion mating with a "pard": a mythical big cat resembling (and possibly based on shoddy accounts of) a cheetah.
They also describe camelopards/cameleopards (giraffes) as being the result of a camel and a leopard mating. Make of that what you will.
The Turkish origin myth had their forefathers being born from sex between a young warrior whose feet had been chopped off and a she-wolf that nursed him back to health.