#Colossal Cuddlefish
Cephalopods have a variety of tricks to obfuscate their appearances. Cuddlefish have the addvantage of using these to hypnotize fish, which sounds rather Cthulhuan. The real challenge is retaining the fancier abilities with gigantism, since Evolution tends to result in abilities being lost if they are not useful enough to be worth the cost (see brains in Echinoderms, or sightless cave-dwellers, or humans' ongoing relationship with wisdom teeth). A Cthulhu-esque giant cephalopod doesn't really need the shapeshifting and hypnosis, unless it's neighbors are similarly enormous.
Perhaps there is a giant cuddlefish population in an environment with other large marine life, but not Cthulhu-sized. A rare mutation causes this creature to get exceedingly large, and one or more of these individuals is particularly long-lived.
Which brings us to the one big problem with cephalopods: lifespan. I'm not sure if this applies to cuddlefish, but when an octopus reproduces, its fate is sealed. This might well be the reason there aren't legions of intelligent octop[pi|podes|pusses] dominating the oceans, since they can't transmit information to their offspring. However, this shortened lifespan has a straightforward solution: sterility. A long-lived colossal cuddlefish is most likely not going to reproduce, even if its smaller brethren do so at the cost of their lives.
While you could replace the hypnotic color effects with chemicals or infrasound, I do find the related cephalopod abilities for stealth relevant. If a colossal cuddlefish has much more dynamic uses of its stealth abilities, well, it won't be very stealthy (what with being gigantic and all), but it will allow it to look far more Eldritch than your typical, already out-there cephalopod.
The hardest issue is the flight. Cephalopods can survive out of water for short bursts, but giant creatures suffer a penalty from their own weight when leaving the water. So right off the bat, a colossal cuddlefish is less likely to fling itself over a barrier. It most likely cannot reshape its flesh into something aerodynamic, and it would not have an obvious means of filling itself with a gas that could help it stay aloft for any significant time in air. If it can inflate itself by accumulating gas in its body, that can support some of the other features - giant but not too giant (the inflation makes it look bigger), the ability to produce terrifying noises you'd not generally expect from cephalopods, and much more support in air than you'd expect for such a large and squishy creature.
So Cthulhu is a giant, celebate, mutant cuddlefish that inflates itself like a balloon, and probably "flies" by expelling the gas, doubtless mixed with water or some other fluid to make it look less like a giant deflating balloon and more like alien geometry as its image is refracted in the mist. It retains enough shapeshifting to make pinning down its true appearance difficult while it yet lives, and its ability to alter its color and generate sound can mess with the minds of many a creature. An evolutionary reason for the gas is the primary mystery. Perhaps the gigantism made it vulnerable to gas-producing gut microbes over the centuries? This would help it to support its weight and get around more efficiently, but would be unlikely to be a default feature of this species.