So Cthulhu will be disqualified for any number of legal reasons (although there are no fictional characters blockers BUT the fact that he was not a legal resident of U.S. Territory at the time it became U.S. Territory.). The United States recognizes both Jus Soli and Jus Sanguinis (citizenship by birth in territory, citizenship by parent citizenship) as counting for Natural Born Citizen. As such, you would have to prove that Cthulhu was either living in present day U.S. Territory (or was born in territory formerly held by the U.S. but no longer U.S. Territory. Given his enternal slumber in the Pacific ocean, this is highly unlikely) or that his parents were U.S. Citizens (again, impossible, as I'm not sure of the circumstances of his parantage, the fact that he predates the U.S. means that his parents could not be U.S. Citizens).
So, lets say this was a massive write in of a person who was not qualified to be President. These votes would be disqualified by the fact of disqualifications of the candidate to legally serve as President (Natural Born Citizen of age 35 or over and 14 years living within the nation) and would be counted as if they did not choose the vote at all. Each state would determine who the runner up in the race is and declare them the winner (and save for two states, they would take electoral all votes for that state). Supposing that the candidates are either of two big parties were next, they would get those points, even if Cthulu had 93% of the vote in that state.
Should there be a massive write in and no candidate gets a victory (271 votes), congress will determine the winner in a special session. I believe the House chooses the President and the Senate will choose the vice president, though it may be reversed. It will be the incumbent legislature, rather than the newly elected (the House is potentially a lame ducks at this point, as is 1/3rd of the Senate).
For a common analogy, think of the electoral college vs. popular vote as a Baseball League vs. a Soccer League and that the points scored are the votes.
Baseball will send it's to best teams to a league contest, which is played in a Series of games (The World Series is best 4 games out of 7). It doesn't matter that the second place team had a blow out in two of their three victories and thus, through the entire series, were the stronger point getter, the winning team was able to win four games to their three and thus are the champions. Conversely, Soccer tallies all points scored over all games played and the team that scored the most points is declared the winner, even though they might not have the most game wins. (This is a major plot point in Harry Potter, as Quidditch leagues are run the same way. In at least one point, the final game is between the Slytherin and Gryffindor teams. Slytherin had scored 200 points more than Gryffindor prior to the match, and thus, Gryffindor not only need to catch the Snitch (150 points) but needed to maintain a 60 point lead before they could get that 150 (and take the trophy with a 10 point lead over the second place team). There were several parts during this match where Harry had to prevent an early capture of the Snitch by both him and his opponent because the score was only 30 up.).