You can find detailed algorithm descriptions for fmincon here and compare them to algorithm descriptions for lsqnonlin here. There are substantial differences in the selection of minimization algorithms available and how they work. FMINCON, for example, doesn't support an option to use Levenberg-Marquardt, unlike lsqnonlin. Mathworks also has a page with its recommendations for algorithm selection
The simplest answer is that fmincon uses fancier algorithms than lsqnonlin and lsqcurvefit because fmincon must be able to deal with nonlinear constraints, whereas lsqnonlin/lsqcurvefit do not. Therefore, if you apply fmincon to a simple bounded least squares problem with no nonlinear constraints, it may invest more computation than you really need.
This is not a perfect rule, however. lsqnonlin algorithms all use first derivative information only, whereas some fmincon algorithms let you use second derivatives as well. This can be a benefit to convergence speed, though how significant will depend case-by-case on your problem.
The bottom line is that completely optimal algorithm selection requires experimentation...
