On a number of occasions, e.g. S07E21 with Odo, Changelings give a sample of themselves for studies. As they don't seem to eat or consume, are they permanently losing mass when they do so? They seem to show little more hesitation than someone giving [replenishable] blood.
In the episode The Begotten the infant Changeling grows, indicating that Changelings do increase in mass. Where this mass is coming from is never really revealed (as your said, they don't seem to eat), but the infant's size did stagnate when it was not being encouraged to shape change, perhaps indicating that this is somehow a factor.
It is fairly clear throughout the series that Changelings can drastically change their size (shifting into birds, fog, etc.). This would mean either a change in density, or a change in mass.
However, their weight when smaller also appears to be less. For instance, in the pilot, Odo changes as a sack to hold latinum, and the sack does not appear to have the weight of a grown man. Thus it seems that they are able to change their mass (however that may be).
When the female Founder gives her "skin" samples to Weyoun for Dominion scientists to find a cure for her disease, it doesn't appear that she expects it to be returned (the previous sample(s) had run out, so presumably the tests destroy the samples). However, when Odo gives a sample to Bashir, he tells him that he expects it to be returned.
So it's possible that, being a much older and more powerful Changeling, the female Founder can regenerate lost mass more easily or has more mass to give, or perhaps she can replenish her body mass when she returned to the Great Link.
Also, DS9 writer, Robert Wolfe, theorized that when Changelings morph to a smaller object, they shift part of their mass into subspace. So it's possible that the way they gain energy/grow is through some subspace interaction.