Like the Mi-Go and unlike the Elder Things, the Spawn of Cthulhu are not made out of ordinary matter at all, and seem to possess shape-shifting abilities to some degree. They were noted for the non-Euclidean geometry and strange angles of their architecture. Unfortunately for them, most of the land areas that belonged to the Spawn of Cthulhu ended up sinking back to the sea, including their most sacred stone city of R'lyeh, where Cthulhu himself still lies dormant. While the origins of the octopoid creatures is not clear, two hypothesis could be speculated upon: that they were a species that simply happened to be extremely devoted to Cthulhu (who as should be noted shares some cephalopod traits with them) or that they were created by him, perhaps even as true off-springs. The fact that some other Great Old Ones also appear to have "follower races" (such as Dagon, who is worshipped by the Deep Ones, for example) could possibly support this.
Appearances - At the Mountains of Madness by H. P. Lovecraft (do not really appear, but are described in the art works of the Elder Things)