The dynamically generated effective gluon mass is known to depend non-trivially on the momentum, decreasing sufficiently fast in the deep ultraviolet, in order for the renormalizability of QCD to be preserved. General arguments based on the analogy with the constituent quark masses, as well as explicit calculations using the operator-product expansion, suggest that the gluon mass falls off as the inverse square of the momentum, relating it to the gauge-invariant gluon condensate of dimension four. In this article we demonstrate that the power-law running of the effective gluon mass is indeed dynamically realized at the level of the non-perturbative Schwinger-Dyson equation. We study a gauge-invariant non-linear integral equation involving the gluon self-energy, and establish the conditions necessary for the existence of infrared finite solutions, described in terms of a momentum-dependent gluon mass. Assuming a simplified form for the gluon propagator, we derive a secondary integral equation that controls the running of the mass in the deep ultraviolet. Depending on the values chosen for certain parameters entering into the Ansatz for the fully-dressed three-gluon vertex, this latter equation yields either logarithmic solutions, familiar from previous linear studies, or a new type of solutions, displaying power-law running. In addition, it furnishes a non-trivial integral constraint, which restricts significantly (but does not determine fully) the running of the mass in the intermediate and infrared regimes. The numerical analysis presented is in complete agreement with the analytic results obtained, showing clearly the appearance of the two types of momentum-dependence, well-separated in the relevant space of parameters. Open issues and future directions are briefly discussed.