Sorry, but you can't force fsolve to have this behavior, since that would require re-writing fsolve. It simply is not one of the available options.
If you are getting that many function evaluations, then it is almost certain that you have very many variables. Large problems require a lot of function evaluations. Just wanting something to take less time is not enough, unless your name is Harry Potter.
So while you don't say how many unknowns, this is surely a quite large problem. Since fsolve uses finite differences to compute the Jacobian at each iteration, this is certainly why it takes so many function evals per iteration. Most of them are spent on just computing the derivatives.
Some people may choose to suggest that you supply the Jacobian separately. Sorry, but that is almost never a real gain in speed, because computing those derivatives will take a large amount of time, even if you can do so analytically. So if you have n unknowns, and your function requires time T to compute one function evaluation, then computing the Jacobian matrix numerically will require roughly (n+1) function evaluations using finite differences. So the time is roughly O(n*T). As it turns out, computing the derivatives of a function is often more complicated than computing the function itself. But even if each of them also requires time T to compute, then the Jacobian will still require O(n+T) time to compute. So you gain essentially nothing at all.
Big problems require big time.
