No "cashing in"
Before Star Wars took the world by storm in 1977, Gene Roddenberry and Paramount were planning a television sequel to the original Star Trek series, to be titled Star Trek: Phase II. One of the episodes penned for the new series was called "In Thy Image", by Alan Dean Foster (based on a script by Roddenberry called "Robot Return", originally intended for a different show).
When Star Wars (and also Close Encounters of the Third Kind ) proved that science fiction films could enjoy wide success, Paramount switched gears and green lit a Star Trek film, thus putting Phase II on hold for a decade (until it could be realized as The Next Generation ). The episode "In Thy Image" was lengthened and adapted for feature length and became what we know as The Motion Picture.
So in a sense, the first title of The Motion Picture was "In Thy Image".
As early as July 19, 1978, the film's shooting script was entitled Star Trek: The Motion Picture.
As for why The Motion Picture and not "The Movie":
The amazing popularity of Star Wars: Episode IV - A New Hope (1977) had a definite impact on the storyline, pacing and even marketing of Star Trek: The Motion Picture (1979). Many hardcore sci-fi fans (including prominent sci-fi writers) viewed Star Wars as mere fantasy, an updating of Buck Rogers/Flash Gordon level matinee fluff. Gene Roddenberry always saw Star Trek as a more serious endeavor, and did not want Star Trek: The Motion Picture to be seen as "cashing in". So the story for Star Trek: The Motion Picture was pushed toward more sophisticated and complex ideas, the decision was made to have no battle scenes of any type. In fact, the earliest Presskit promotional material for newspaper ads had as the main line, "There is no comparison".
Given Roddenberry's decision to have lofty ideas and no battles in the film as part of an effort to keep Star Trek above what he considered "fluff", the choice of The Motion Picture over The Movie seems consistent with this.
Side note: In Germany, the film was called Star Trek: der Film (i.e. Star Trek: The Film or Star Trek: The Movie ).