OK, we are going to Fermi Estimate this. TL;DR: about 1.5 Billion years.
Mars can never be terraformed and left alone. That is, we can never "finish" terraforming it, and will always have to replenish its atmosphere. It is simply too small and there is too much of a problem with solar wind stripping its atmosphere away. As a result, whether it can gravitationally hold on to its O2 and N2 is not important, since solar wind will always remove it.
However, that begs an important question: what level of terraforming are we talking about? There are several possibilities, of which I will study 2.
The dynamo kickstart method: Presume that you somehow did produce a large planetary magnetic field on Mars. This would be required no matter what if you want people to survive, since otherwise we'd be showered with a constant stream of high energy particles. In this method, Mars never loses most of the atmosphere you've given it, and it stays terraformed. This is boring.
The "magnetic field generators broke" method: no matter what, the terraformed Mars required a magnetic field. However, it was clearly abandoned. Why? Because its magnetic field generators broke, that's why, and they require such a tremendous amount of energy and cost to create that you just couldn't make another one. Perhaps your society collapsed and only a lucky few escaped to the primordial Earth, allowing Mars to die slowly.
So to the question: how slowly? As stated in the comments, we need to discuss the difference between "totally undone" and "measurably undone". In your question, it seems that you are asking:
Presuming that Mars was terraformed very long ago and then suddenly maintenance stopped, how long would it take for it to become indistinguishable from today's Mars, at least according to our best science?
The answer to that question is: exactly as long as Mars has existed for. So let's answer the other one: how long until Mars is uninhabitable.
It appears to be the case that the Sun, long ago, was much more active and thus stripped Mars' atmosphere away a lot faster in the past than now. That link also says something interesting: the rate of atmospheric escape on an early Mars appears to be around 6-7 times more than it is currently, which is about 1500 grams of atmosphere per second. So let's make the assumption that Mars' atmospheric escape was 7x1500 = 10500 g/s once the magnetic field generators turned off, or approximately 900,000 Kg per (modern) Earth day, and it is down to approximately 130,000 Kg per modern Earth day now.
Earth's current atmosphere weighs approximately $5\times10^{18}$ kg. Mars is about 40% the size of Earth, so let's make our lives easy and assume that its early atmosphere weighed $1\times10^{18} kg$ just before the magnetic field turned off.
Assuming that the rate of atmospheric loss reduces exponentially (which it PROBABLY does, but it also probably depends so strongly on so many other things that this is a WILD guess) the rate of loss is:
$$R_{loss} = 900000 e^{-1.3E-12 t}$$
where $t$ is in days.
We can finally solve for $t$ by making a HUGE assumption: the rate of atmospheric loss is directly proportional to the atmospheric pressure. That is:
$$P = \alpha R_{loss}$$
We don't need to know what $\alpha$ is. Watch:
Humans have survived for two years at 0.475 atmospheres of pressure, and this is the highest recorded survival, so let's assume that once the atmosphere of Mars reduces to 0.475 of its former pressure, Mars' terraforming has been "undone". Since we've assumed that $R_{loss}$ is directly proportional, this is equivalent to saying that $R_{loss}$ has decayed to 0.475x900000, or 427500 Kg per modern Earth day. The time it takes to do this is:
$$t = -\frac{\ln(\frac{427500}{900000})}{1.3E-12} = 5.5E11$$ days.
This is approximately 1.5 Billion years.
