Why do nested loops multiply their running times instead of adding them?

Two nested loops multiply because the inner loop is not run once: it is run in full for every pass of the outer loop. A thousand outer passes, each containing a thousand inner passes, is a thousand groups of a thousand, which is a million.

By hand it is three lines, in this order. How many times does the outer loop repeat, in terms of the input size $n$? What does one pass of the outer loop cost, which is the whole inner loop? Multiply. A single pass over a list of a thousand items is a thousand steps. Put that pass inside another pass over the same list: the outer repeats a thousand times, and each of those times a fresh thousand step job runs, so the total is one thousand runs of a thousand steps. Two loops side by side are different in kind. The first finishes entirely, then the second begins, so the work is a thousand steps followed by another thousand steps. Nothing gets repeated on anybody else's behalf, and the totals are a thousand times apart.

The guess that fails is to see two loops and count two loops' worth of work, then add. That is exactly right when the loops are siblings and exactly wrong when one sits inside the other. Adding counts the inner loop as though it were paid for once, which is the cost of the first outer pass only; the remaining 999 passes each pay it again. The tell is in the numbers above. If adding were correct, the nested loop would cost 2,000 at a thousand items, and doubling the input would double the run time. It does not double. It goes from 10,000 to 1,000,000 when the input goes from a hundred to a thousand, a factor of a hundred.

A loop over $n$ items whose body asks whether $x$ is in a list has two loops in it, and only one of them is spelled for. The membership test walks the list until it finds a match or runs out, so its cost grows with $n$, and that cost is charged on every outer pass: $n$ passes of an $n$ step scan is $n^2$. At ten thousand items that is 100,000,000 counted steps against the 10,000 you would count if you priced the test at one. Swap the list for a set and the same test becomes a constant time hash lookup, the body costs one step, and the whole thing collapses to $n$. The two versions read identically; they differ by an entire rung of the ladder.

Three things move it. If the inner loop shrinks as the outer advances, say it runs $i$ times on pass $i$, the total is the triangular sum below, still quadratic but with half the constant. If the loops run over different things, $r$ rows and $c$ columns, the total is $r \times c$, which is linear in the number of cells and quadratic only when $r = c$; this is why calling a grid traversal quadratic without saying in what starts arguments between people who are both right. And a third nesting multiplies again: a thousand cubed is a thousand million.

The rule also stops applying the moment the repetition count stops depending on what is left. A loop that removes ten items per pass from a million runs a hundred thousand times, not twenty, because removing a fixed number of items is still a linear pass whatever the constant. Only removing a fixed fraction divides what is left each time, and that is the pattern that costs the logarithm: $10^6$, then $5 \times 10^5$, and so on down to one, is about twenty passes. Multiplication is what repetition inside repetition does; how many times the inner thing repeats is a separate question, and it is the one that decides between the rungs.