I'm an amateur at this whole speculation thing so don't take the following too seriously.
Since Mars atmosphere is mainly CO2, and if we did find water of the frozen variety, it would be theoretically possible to plant tons of trees to 'convert' more of the atmosphere to breathable air. Oh course you're have to terraform like 90% of the planet for that to work with any speed but hey, it's a thought, right? lol