Cthulhu has been in the Public Domain for a very long time, since 1969 I think.
But even before that, H.P. Lovecraft himself explicitly stated that he gave permission for others to use his works as the basis for their own.
I just wish we had tentacle face options in the game...
Of course, doing that runs the risk of Hasbro coming after you for Illithid copyrights, sigh...