I think your bonus question directly relates to the main question. Keep in mind, the chinese abacus or suanpan (算盤) was the primary way to do arithmetic back in the day. While today we instruct students to use paper to make calculations (think of carrying the 2, long division, et cetera), paper was much more time consuming to make in the 14th century.

The suanpan solved this problem by having several (usually 13) rods of beads, separated into two rows, one of two beads and one of five. A number could be represented on each rod, allowing thirteen digits to be stored on a single suanpan. Algorithms were developed to calculate sums, differences, products, quotients, square roots, and other common functions on the suanpan. Many students in Asia are still trained on the suanpan or the related Japanese abacus, the soroban.

So if you wanted to save paper (and therefore money), you'd just use one of many algorithms to perform calculations on your suanpan. But think about the way you evaluate polynomials on paper:

f(x) = 4x^3 + 3x^2 + 5x + 7

Today, we'd first plug in a value (say, 2) in for x, then calculate the cube and square, then calculate each term, then finally add them all together. If you're showing your work (and you'd have to, especially for long polynomials), this would mean writing down several numbers per term, therefore using precious paper.

The algorithm used by Qin Jiushao and others of the 13th and 14th centuries appears to be similar to what today's western mathematicians call "Horner's Method," which notes an interesting way to solve this problem. Instead of writing down several numbers for each term in your polynomial (which, remember, you have to keep around until the final sum), you can create a sequence wherein each term only depends on the immediately prior number in the sequence (and the polynomial coefficients).

Wikipedia has a perfectly good write-up of the proof, but the jist is this: if the coefficients of your polynomial are a_0 through a_n (where a_0 is the zero degree term, a_n the n degree term), then define b_n as equal to a_n. Now let b_(n-1) equal a_n-1 + b_(n) * x, where x is the value at which we wish to evaluate our polynomial. If we iterate until b_0, we arrive at the proper value of f(x).

This trick allows us to greatly reduce the number of numbers we have to record at any given time by summing "as we go." So we use less paper and less time. Modern computers still use this method, especially for embedded hardware with limited ALUs.

And being able to evaluate polynomials is enormously helpful! Many functions in math are well-approximated by polynomials (though, admittedly, not all of these approximations were known to 14th century mathematicians). Fast and efficient means of evaluating polynomials also helps efficient approximations of solutions (particularly useful for degree five and higher polynomials, which cannot be solved in closed form in the general case).

As a follow-up, when that article says "solving", does it mean finding the roots of the polynomial or evaluating a polynomial at a given point? I would normally take "solving an equation" to mean the former, but I don't think that would have been possible in general before the development of calculus. Unless there's more to this fan fa thing than I realize?

EDIT: Or were they finding roots using something like the bisection method, and using fan fa/Horner to make that tedious process more efficient?

I think the Wikipedia entry is wrong re the highest degree of equations, as far as I am aware the highest attested in Chinese mathematical literature is 10. Specifically in Zhu Shijie's book Problem 18 of Chapter I is an equation in degree 10.

The assertion that Chinese mathematics was inherently practically motivated is likely not universally valid. Let's put it this way: by and large, mathematics in China was motivated by practical concerns, but there was a small number of Chinese mathematicians who were genuinely interested in explorations of mathematical patterns per se and developed sophisticated algorithms to push the boundaries of what could be precisely calculated. From the prefaces to the extant texts it seems that they believed in a connection between mathematical patterns and more general cosmic patterns, often involving the hexagrams of the Book of Changes, motions of heavenly bodies and interactions of the five phases (earth, metal, water, wood and fire). Zhu Shijie would likely belong to this group. So even though calculations of equations of degree three and four could have some practical use in calendrical astronomy and management of public works, people like Zhu pushed the universal method created to solve these practical examples to higher degrees to show off their mastery of the method and its inherent power, rather than to solve any immediate problem.

The "dimensions of walled cities" were not a practical problem when we talk about these higher degree equations, they were only used to give some geometric meaning to the abstract quantities entering the calculations. In fact all problems in Zhu Shijie's book operate with the same dimensions 3,4,5 (the basic Pythagorean triple) known in advance, so they are basically placeholders which enable easy calculations.

The calculations were done partly with counting rods on any suitable surface and partly with an extremely condensed form of written notation, so the amount of paper needed to do this was surprisingly small.