Quantitative models of sunspot and starspot decay predict the timescale of magnetic diffusion and may yield important constraints in stellar dynamo models. Motivated by recent measurements of starspot lifetimes, we investigate the disintegration of a magnetic flux tube by nonlinear diffusion. Previous theoretical studies are extended by considering two physically motivated functional forms for the nonlinear diffusion coefficient D: an inverse power-law dependence D ∝ B⁻ᵛ and a step-function dependence of D on the magnetic field magnitude B. Analytical self-similar solutions are presented for the power-law case, including solutions exhibiting "superfast" diffusion. For the step-function case, the heat-balance integral method yields approximate solutions, valid for moderately suppressed diffusion in the spot. The accuracy of the resulting solutions is confirmed numerically, using a method which provides an accurate description of long-time evolution by imposing boundary conditions at infinite distance from the spot. The new models may allow insight into the differences and similarities between sunspots and starspots.