It really depends on how you define coincidence. (This is long, since it involves background from several aspects of Star Trek -- but I provide links to some cool behind the scenes books, including one that has copies of two never-produced scripts for a Star Trek show that almost was and the other has the original draft of Harlan Ellison's The City on the Edge of Forever.)
Gene Roddenberry had some specific tastes, and one was the indestructible foe. This shows up in many storylines throughout Trekdom, at least as long as Roddenberry was alive. We see a taste of it in The Cage, where Captain Pike comes up against the Talosians, and again in the next pilot, in Samual Peeple's script for Where No Man Has Gone Before, but those antagonists are people, with many ways to defeat them.
Better examples would be the large ship in The Corbomite Maneuver, The Squire of Gothos, Landru (who was really a computer) in Return of the Archons, The Changeling, Vaal, in The Apple, and The Doomsday Machine. (This is where I stopped looking, but I suspect you won't find many in TOS, Season 3, since Roddenberry wasn't Exec Producer at that point, due to NBC calling him out on what he hoped was just a bluff.)
This theme also re-appears in Star Trek: The Next Generation in the form of Q. Even after Roddenberry was not as active in the show (old and not in great shape, from what I hear), we see the Borg show up in Q Who.
Roddenberry liked godlike beings that seemed unstoppable and notice that if this being or entity was something that could be communicated with, it was usually defeated by Kirk having a logic argument and creating some kind of infinite loop (we also see this in I, Mudd). This doesn't happen in every one, for instance, there's no way to communicate with the planet killer in The Doomsday Machine. Of course, later, it was Picard, and he essentially did "out logic" Q to a point in the courtroom scenes and did something similar in Q Who by doing what Q did not expect and admitting he wasn't able to defeat the Borg.
Roddenberry had this big issue with a need for big, heavy, and severe danger. Harlan Ellison commented on this when he referred to his experience in writing City on the Edge of Forever, in his book The City on the Edge of Forever. He comments that Roddenberry would call him and say, "The ship has to be in danger. BIG danger!" (He also said Roddenberry would blame that on the network and that a good story wasn't enough -- the Enterprise had to be seriously threatened.)
(The link is to a copy of that book on Amazon. I recommend the book, since it gives an interesting view of Ellison's experience as well as the original draft of the script for The City on the Edge of Forever.)
Roddenberry had a need to make the viewers feel a serious threat - he loved it and used the godlike being or the unstoppable, indestructible foe many times. (Yes, often this makes for a good story -- pitting the protagonists against an antagonist stronger than they are, but you can only recycle a plot but so many times.)
Now, to get the rest of this, it helps to know about the Star Trek show that almost was: Star Trek: Phase II. In the 1970s, due to the rising popularity of a show everyone expected to just disappear, Paramount was interested in launching a new Star Trek series. So they started work for Star Trek: Phase II. This series would feature the original cast, other than Leonard Nimoy, and included three new characters: Xon, a Vulcan (who would essentially replace Spock), Ilia, the ship's Counselor, and Stephen Decker (who was supposedly the son of Matt Decker, who died in The Doomsday Machine) as the ship's XO, who would be the new hero who would go on landing parties instead of Kirk.
You can find out a lot of fascinating details about this in Star Trek: Phase II, The Lost Series. It's an amazing look at how the series almost was, then wasn't. They had story outlines and even scripts ready for a new series.
But along the way, another show from the 1960s (sorry, I can't remember which one) ended up as a movie and actually did well at the box office. So Paramount decided that it'd be even better to make a movie, instead of a TV series. A good movie would bring in big bucks and after the movie was done, they could either make sequels or go for a TV show.
The 2 hour pilot for Star Trek: Phase II (written by Alan Dean Foster) was another great example of Roddenberry's craving for godlike beings, right down to the title (In Thy Image). While there's nothing in the book to indicate that the intent was to clone The Changeling from the original series, considering Roddenberry's love of godlike beings, and his feeling that they were great drama, it makes sense that for a series pilot, he'd want to kick off with that kind of concept.
When the change was made to make a movie instead of a TV series, for some reason (I don't know production timing -- they could have been in a hurry), they just grabbed the 2 hour script In Thy Image and re-wrote it to include Spock (and Xon was essentially written down to one brief scene with Kirk and one scene where he died in a transporter accident -- and was later just left on the cutting room floor.) Ilia was changed to the ship's navigator, since introducing a new role that would be hard to explain in a few lines did not make sense for a 2 hour movie. And then they added hours of special effects scenes to make it feel more "big screen-ish."
You can read the original 2 hour script for In Thy Image in the book I liked to above, along with the script for The Child (later made into a ST:TNG episode), and story outlines for a number of other episodes (at least one other also became an episode in ST:TNG and one story included what may be a precursor to the idea of the Borg).
The intent was to stick with what Roddenberry thought would be the strongest concept for a series pilot. He liked godlike beings, so he picked one for the pilot for STPII and when they changed it to a movie, they just stuck with that script. So you can call it coincidence, but it's more just because Roddenberry liked that concept.
(Trek fans may want to watch ST:TMP on a small screen sometime and notice it plays better on TV than it did on a big screen when it seemed empty. That's because it was originally written for TV and was never given a proper re-write when it was re-purposed for the big screen.)