The concept you are referring to is speciation and it has been well studied in a wide variety of different natural organisms. I suppose here we are talking about the biological species concept.
The overall answer is yes it is possible, but critically depends on a few different factors. The reality of speciation in the wild is very complex, but these are some things to consider:
Genetic isolation
If two groups, such as your Martian colony and humans on earth isolate from one another, then for speciation to occur, there needs to be a significant level of genetic differentiation between them. This means substantial differences in the kinds of genetic variants found at positions along the genome.
Genetic differences are eroded by post-isolation gene flow – in your example, that might mean a spaceship flying back to Earth with Martian colonists, who then have offspring with people on Earth.
Although there is plenty of evidence that speciation with gene flow can occur, the general rule of thumb is that increased gene flow means a longer divergence time is required to fully speciate.
In nature, this is often caused by some kind of geographic barrier to gene flow, such as mountains or rivers forming, but it can also be caused by morphological differences, such as variation in sexual appendages. Of course, in our example, this barrier to gene-flow would be the large and difficult to traverse distance between the Earth and Mars.
Divergence time
You alluded to some kind of separation time, and you are right to be talking on the scale of millions of years. Speciation can occur extremely quickly; in Lake Tanganyika cichlids, it has occurred probably within the last 15,000 years. Humans have created whole new species of crops, such as maize, within the past 10,000 years. There is even evidence of some fish speciating in 3000 generations.
However speciation is often a much longer process. For example humans and chimps were thought to speciate in 4.5 millions years.
Of course, there is an interaction with several other factors. All other things being equal, less post-isolation gene flows results in a shorter time to speciation and vice versa. Stronger selective pressure between the different environments leads to a more rapid accumulation of genetic differences.
As Konrad Rudolph correctly points out, divergence time is strongly related to generation time, with all other things being equal, a shorter generation time, results in faster speciation.
Selection pressures & differing environments
I think the last main factor governing speciation is how different the Martian colonists environment was from that on Earth.
Different environments can lead to natural selection occurring in opposing directions in the two populations, leading to ecological speciation. Speciation can proceed without differing environments, where neutral drift in allele frequencies can eventually cause speciation, but this will be a long process.
Speciation will occur much more rapidly if there is a start difference in environment and selection pressures between the two groups.
So in conclusion, given enough time, genetic isolation and differential selection pressures (or some combination of the above), it is plausible that a new species of human could form. However, given the time-scales required, it seems a bit unlikely to me.
EDIT
I think it is worth pointing out what @Jaquez said in the comments. If current terrestrial humans split from an extraterrestrial source to form another species, it would be named as another species within the Homo, such as Homo extraterrestrialis, for example. The addition of a new species does not move the group Homo up to become an e.g. Tribe or Family.