Air breathing is a 3rd-level transmutation for clerics, druids, sorcerers, and wizards that lasts 2 hours per level (e.g 10 hours at the minimum caster level 5th) and allows a creature that normally breathes water to instead breathe air (it is exactly the opposite of respiração de água). It’s printed in several books: Campeões da ruína, Espécies Selvagens, Stormwracke Compêndio de Feitiços. A continuous item of respiração aérea would, per the orientações (which are only guidelines, check with your DM), cost 30,000 gp. I would value it less than that.
Stormwrack e Espécies Selvagens também têm fins to feet, a 2nd-level transmutation for druids, sorcerers, wizards, and weirdly enough, spellthieves, that takes a creature with a swim speed and gives it a land speed instead. For a Large or larger creature (like an aboleth), that would be a speed of 40 feet. Unfortunately, it also costs the aboleth its tentacle attacks, and it only lasts 1 hour per level. As a continuous item, per guidelines, it costs 12,000 gp. It isn’t really worth that much, so your DM may be willing to price it below that guideline.
Anyway, beyond walking, there are a large variety of ways to gain a flight speed; the cheapest, at 10,000 gp, is a feathered wings graft (Fiend Folio), but unfortunately now that your aboleth is no longer evil, those will drive it mad. Check Listas de Ernir de itens mágicos necessários for other approaches to flight, though. A tapete voador might be the best thing, at 20,000 gp.
None of these deal with an arguably-bigger problem for this aboleth: drying out. Aboleths need to remain immersed in water in order to survive; per Senhores da Loucura page 17, if one is out of water for more than a few (“excruciatingly painful”) hours, they will enter “the long dreaming,” in which they cannot act, and which aboleths consider “a fate worse than death.” Some few aboleths, known as amphibious aboleths, can tolerate living in swamps and the like; see Senhores da Loucura page 20. Conjuring water, putting a gigantic tank of water on that tapete voador, and so on, could be solutions, but they’re all going to be awkward at best.
Além aquele, there is the polymorph option your DM suggested.
Senhores da Loucura describes an uobilyth, an “‘aerial aboleth’ as they are known to the few who have encountered them.” These “do not have the aquatic subtype or a swim speed. They gain the air subtype and a fly speed of 60 feet (good).”
Where uobilyths come from, how they form, and so on, is unmentioned. It may actually just be evolution; the preceding section on amphibious aboleths is a result of evolution.1 But anyway, they exist, and they’re very similar to aboleths. That means that polimorfa qualquer objeto, an 8th-level transmutation for sorcerers and wizards, can turn an aboleth into an uobilyth and it’s going to be permanent—it could still be dispelled, but otherwise, the now-uobilyth can fly and breathe air (obligate water-breathing is a function of that aquatic subtype that uobilyths don’t get). Hiring someone to cast polimorfa qualquer objeto for you once costs a mere 1,200 gp, but finding someone capable of doing it may be difficult. A scroll of it costs a minimum of 3,000 gp, and may be somewhat more manageable to find (according to the random 8th-level scrolls table, 3% of 8th-level scrolls are polimorfa qualquer objeto). Since it is vastly cheaper than the other options, having a back-up in case it gets dispelled is likely a good idea. Note that if you cannot yet cast 8th-level spells yourself, it is a DC 16 caster level check to successfully cast it (and if you fail, it is a DC 5 Wisdom check to avoid a mishap).
Polimorfa qualquer objeto could also, as your DM suggested, turn an aboleth into a phoenix. That would probably also be permanent, assuming that it doesn’t get extra Intelligence for being a phoenix (unlikely, aboleths are super-Intelligent to begin with). The uobilyth is probably stronger and doubtlessly, at least in my opinion, cooler.
Finally, just... a word of caution. An aboleth is a preposterously overpowered as a familiar. Aboleths are some of the most fearsome and dangerous creatures in the books; there’s a reason why in, Senhores da Loucura, a book devoted to aberrations, their chapter came first. Playing as an aboleth is dubious in the extreme. Having one as an extra add-on class feature just, I don’t even know, I’m speechless. I get that your DM allowed it. I strongly suggest considering just... not doing that. There’s a really high risk of it damaging the game, overpowering you, trivializing encounters and outshining the rest of the party. I would never, ever allow that in my games.
- Actually, it sounds rather Lamarckian, since it sounds like an individual aboleth can gradually become accustomed to a wet-but-not-immersed life.