When the problem is linear, the Solver will recalculate the model approximately N times, where N is the number of decision variables (or changing cells). This happens once, during the phase when "Setting Up Problem..." appears on the Excel message bar.
When the problem is nonlinear, the Solver must recalculate the model N times on every major iteration, in order to update its estimate of how the objective function and constraints are changing. For this reason, you'll see the Solver spending much more time on each Trial Solution reported on the Excel message bar for a nonlinear problem. Further, on linear problems the Solver is able use faster and more reliable methods to choose the decision variable values for the next trial solution.
We often see Solver models from users who are convinced that their problems are intrinsically nonlinear, yet we find that with a modest effort (sometimes no effort) these models can be set up as linear problems. If solution time is an issue, it is worth your while to consider whether the model really could be formulated as a linear problem. For more information on this topic, consult our Solver Tutorial, or ask for access to our protected Support pages discussing piecewise linear approximations for nonlinear functions.