In 1919, H. P. Lovecraft had a dream, which he described in letters to two friends (Letters to Alfred Galpin 87-88, Letters to Rheinhart Kleiner 188-189), and formed the basis of entry #25 in his Commonplace Book, a sort of journal where Lovecraft included plots. It was as follows:
Man visits museum of antiquities—asks that it accept a bas-relief he has just made—old and learned curator laughs and says he cannot accept anything so modern. Man says that
‘dreams are older than brooding Egypt or the contemplative Sphinx or garden-girdled Babylonia’
and that he had fashioned the sculpture in his dreams. Curator bids him shew his product, and when he does so curator shews horror. Asks who the man may be. He tells modern name. “No—before that” says curator. Man does not remember except in dreams. Then curator offers high price, but man fears he means to destroy sculpture. Asks fabulous price—curator will consult directors.
Add good development and describe nature of bas-relief. [Cthulhu]
Steve J. Mariconda notes in "The Emergence of Cthulhu" (Lovecraft Studies #15, 1987), that on the same day Lovecraft hatched the plot, he had been reading Lord Dunsany - which will be important later.
From this basic idea H. P. Lovecraft outlined "The Call of Cthulhu" April 12-13, 1925, and actually wrote the story a year later in August or September 1926 (S. T. Joshi, I Am Providence 2.600-601, 636-638).
There were several significant influences on "The Call of Cthulhu" - the plot element of creating the bas-relief in dreams is evident from Guy de Maupassant's "The Horla" (1887); Theosophy, with its cosmic cycles and strange entities that came down to the stars:
Old Castro remembered bits of hideous legend that paled the speculations of theosophists and made man and the world seem recent and transient indeed. There had been aeons when other Things ruled on the earth, and They had had great cities.
...and A. Merritt's The Moon Pool (1918), which is set in the strange ruins of Nan Matol in Ponape.
Remains of Them, he said the deathless Chinamen had told him, were still to be found as Cyclopean stones on islands in the Pacific.
But the most immediate influence is the artificial mythology of British fantaisiste Lord Dunsany, which began with The Gods of Pegāna (1905); there is actually a specific reference in "The Call of Cthulhu" to one of Dunsany's stories:
The Thing cannot be described—there is no language for such abysms of shrieking and immemorial lunacy, such eldritch contradictions of all matter, force, and cosmic order. A mountain walked or stumbled. God! What wonder that across the earth a great architect went mad, and poor Wilcox raved with fever in that telepathic instant? The Thing of the idols, the green, sticky spawn of the stars, had awaked to claim his own.
This is a reference to Act III of Dunsany's The Gods of the Mountain:
MAN You were all green, Master, all green in the gloaming, all of rock again as you used to be in the mountains. Master, we can bear to see you in flesh like men, but when we see rock walking it is terrible, it is terrible.
AGMAR That is how we appeared to you?
MAN Yes, Master. Rock should not walk. When children see it they do not understand. Rock should not walk in the evening.
The idea of gods sleeping for a time, seeming dead, appears to be taken from Dunsany's "A Shop in Go-By Street" from Tales of Three Hemispheres:
At that he moved heavily and slowly in way-worn carpet slippers, panting as he went, to the back part of his shop, and I went with him. This was a dingy lumber-room full of idols: the near end was dingy and dark but at the far end was a blue cærulean glow in which stars seemed to be shining and the heads of the idols glowed. "This," said the fat old man in carpet slippers, "is the heaven of the gods who sleep." I asked him what gods slept and he mentioned names that I had never heard as well as names that I knew. "All those," he said, "that are not worshipped now are asleep."
"Then does Time not kill the gods?" I said to him and he answered, "No. But for three or four thousand years a god is worshipped and for three or four he sleeps. Only Time is wakeful always."
"But they that teach us of new gods"—I said to him, "are they not new?"
"They hear the old ones stirring in their sleep being about to wake, because the dawn is breaking and the priests crow. These are the happy prophets: unhappy are they that hear some old god speak while he sleeps still being deep in slumber, and prophesy and prophesy and no dawn comes, they are those that men stone saying, 'Prophesy where this stone shall hit you, and this.'"
The actual physical appearance of Cthulhu:
If I say that my somewhat extravagant imagination yielded simultaneous pictures of an octopus, a dragon, and a human caricature, I shall not be unfaithful to the spirit of the thing. A pulpy, tentacled head surmounted a grotesque and scaly body with rudimentary wings; but it was the general outline of the whole which made it most shockingly frightful.
A number of suggestions have been put forth by fans and Lovecraft scholars over the years; Phillip A Schreffler in The Lovecraft Companion suggested Lord Tennyson's "The Kraken" (1830); Robert M. Price poo-poo'd the idea in the introduction to The Cthulhu Cycle (1996), and suggested the tentacle'd nature of Cthulhu owed something to M. R. Jame's "Count Magnus" (1904), and further notes the close similarities between Cthulhu as an aquatic giant in the last part of "The Call of Cthulhu" and the depiction of Dagon in Lovecraft's earlier eponymous tale.
So the idea of Cthulhu was percolating in Lovecraft for some time; he borrowed portions of concepts from other writers - artificial mythology, sleeping gods and mountainous size from Dunsany; the alien origin and creepy cults from Theosophy (this is actually made more explicit in the text); the telepathic dream-sendings from Dunsany and de Mausauppant - the octopus/dragon mixture is a little hard to pin down, since Lovecraft never went into specifics about his influences on that in his letters, although he did provide a sketch of the idol. But tentacles were not unfamiliar in weird fiction in the period; in addition to M. R. James' "Count Magnus" I would also add Arthur Machen's "Novel of the Black Seal" (1895) and the alien invaders from H. G. Wells' The War of the Worlds (1897-1898), both of which Lovecraft had read.
After "The Call of Cthulhu" was written, Lovecraft developed the idea further, positing Cthulhu as the leader of an extraterrestrial race of "Cthulhu-spawn" in At the Mountains of Madness and a Great Priest and cousin to the Old Ones in The Dunwich Horror. You can read more about that in Price's "Cthulhu Elsewhere in Lovecraft" in H. P. Lovecraft and the Cthulhu Mythos.
Edit: Some others above have written much more thorough and better answers, so if this is posted, please refer to them.
Now, I'm no S.T. Joshi here, but I do know a little bit about Lovecraft, so I'll give this a shot. Below I'll talk a little about the relationship between Lovecraft's works and ancient religions, both whether it was a parody or imitation of ancient pantheons, and how ancient religion inspired Lovecraft's creations and the relationship specifically with Cthulhu to ancient inspiration.
Lovecraft took inspiration for his eldritch 'gods' from a number of existing lores and mythologies, but also from the culture and churning literary and scientific tides of the time. To quote Lovecraft:
"When about seven or eight I was a genuine pagan, so intoxicated with the beauty of Greece that I acquired a half-sincere belief in the old gods and nature spirits. I have in literal truth built altars to Pan, Apollo, Diana and Athena, and have watched for dryads and satyrs in the woods and fields at dusk. Once I firmly thought I beheld some of the sylvan creatures under autumnal oaks..."
This would suggest that Lovecraft was informed and inspired at least in part by ancient pantheons, but there's a debate as to whether he was seeking to invoke a pantheon or religious standard to his creations. The idea that he was mimicking a pantheon is mostly present in his followers like August Derleth, who continued Lovecraft's legacy and is mostly responsible for maintaining and then popularizing Lovecraft, saving his works from obscurity. Lovecraft himself never really codified his works officially into a coherent narrative or lore- the "Cthulhu Mythos" were a product of Derleth and his camp of things.
While it's absolutely true that Lovecraft did set up an extensive network of being and interconnected stories, it's difficult to say that there was an intentional structure. Much of what we know as the Mythos is so because of this interconnected work, which was less intentional and more haphazard. Lovecraft and his fellow weird fiction writers often sent nods to each other and kept references to each others' works within their own writing. Sometimes this would make sense and would live on to branch out into a further mythology. One example is the case with "The King in Yellow", a short selection of stories by Robert W. Chambers which was incorporated via references into Lovecraft's works, and then fully meshed into the Cthulhu Mythos later on when the lore of that world was fleshed out by Derleth and subsequent authors. Other times, these references created bridges that were less logical- a good example being that the entirety of the lore of "Conan the Barbarian" is technically accepted in the Mythos due to these intentional references and adoptions. Lovecraft made extensive references to his own works as a way of adding some substance to his spooky tome or local cult. In some ways, this adds to the lore. In others, it creates contradictions.
Lovecraft also made heavy use of the nebulous understanding of ancient religion and occultism in other times, relying either on the misunderstanding or the lack of clarity of eastern religions and European paganism. A common theme is connecting beasts and beings to worship in East Asian traditions, like likening his creation of the Mi-Go to the Yeti, or referencing cults being borrowed from the Orient, brought over by traders or sailors. The times when we see Lovecraft's cults in actual worship, they're often described as being with Oriental, Polynesian, or African characteristics or origin. Sometimes he invokes Egypt, even going as far as to directly shed light on the ancient Egyptian religion in works like "Under the Pyramids"/"Imprisoned with the Pharaohs". Often times he goes for witchcraft, connecting the "ancient witch cults" of Europe with his creations and cults.
But, to get back tot he question, how does this inform his own creations in their design? Some of his characters are clearly inspired by ancient pantheons: Hypnos, for example, appears in a story of the same name and is borrowed almost entirely from a god of the same name in Greek mythology. Other times, Lovecraft invokes ancient religion to lend weight or credibility to his beings: Shub-Niggurath is meant to reference the goat imagery of Satyrs and Pan of ancient Greece, but also the Horned God of witchcraft. Nyarlathotep is invoked as an ancient Egyptian god, who was (in Lovecraft's fiction) the inspiration for gods like Set and Thoth. Dagon shares a name with an Sumerian deity, but not much else, other than being a water-related creature.
However, much of his well-known gods are mostly original. It's not out of hand to speculate that Lovecraft found inspiration for his depictions amongst other myths that aren't explicitly stated in his works. Given the extensive use of borrowing from other mythologies, real and literary, you could assume that he was inspired by sea serpents, mermen, and the kraken for similar beings: fishmen of Innsmouth, amphibious moon men of Ib, and the giant cephalopodic Cthulhu. It's a stretch, but not unlikely. Other creations seemed to be completely original and outside of ancient influence: Yog Sothoth, perhaps the premier being of Lovecraft's "pantheon" (he once jokingly proposed his mythology be referred to as "Yog Sothothery"), is unlike anything else in ancient religion as a swarming mass of globes and portals. The concept of a potentially sentient, unseen of color in "The Color Out of Space" is decently unique for the time. Azathoth, an idiot mass at the center of the material universe, whose fluting and sounds maintain the state of the universe, is perhaps inspired by the "blind, idiot god" trope, but not similar to much in terms of ancient inspiration. For every anciently inspired or invoking being, Lovecraft has another that can't be easily traced beyond his contemporary weird fiction culture.
Basically, we don't really know. It's likely that it was an original creation, simply thought of by combining elements that made sense for horror- the alien appearance of the octopus, the giant size to dwarf we insignificant humans, the human-like body form to suggest sentience, the wings because, well, wings. But we can't rule out the idea that it was inspired from something else, either, just not so explicit as some of his other creations.
S.T. Joshi, in "An H. P. Lovecraft Encyclopedia", suggests that the "Call of Cthulhu", the story that reveals Cthulhu in the Mythos, is an extensive reworking of Lovecraft's previous short story "Dagon", an early story about the dragon-fish-like deity Dagon, itself inspired from a Sumerian and Caananite deity of the same name. The connection between ancient Dagon and fictitious Dagon is scant, though- ancient Dagon has some affiliation with fish or water, but is hardly the inhuman beast described in Lovecraft's work (though he also describes the beast as "Polyphemus-like", invoking a reference to the cyclopes son of Poseidon). There are similarities between the stories- unwitting seafarers end up on a south Pacific island, where they encounter strange structures suggesting ancient and forgotten culture, before coming in close contact with a sea-beast god, after which they barely escape back to civilization where they worry that certain astronomy (a waning gibbous moon in "Dagon", aligned tars in "The Call of Cthulhu") will resurface the island and bring the beast to bear on humanity.
The long and short of it here is that Cthulhu is likely evolved from Lovecraft's previous being Dagon, itself a morph of some aspects of the ancient deity Dagon, with plenty of sea-faring lore thrown in. Beyond that, the actual depiction is likely mostly original, drawn up to combine the most alien and awe-inspiring traits Lovecraft could think of at the time.
See also: