Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?
There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance.

One of them is parallelism, as you point out.

A second technique trading off more transistors for performance is speculation.  Often speculative execution of some kind is combined with parallelism, and this kind of performance optimization happens at all levels.  For example:
A carry-select adder compputes both a+b+0 and a+b+1 and then selects the correct answer when the carry bit becomes available.
In predicated execution we might execute instructions before we know their results are needed, and then commit the results to the register file only once we know the computation was needed.
In checkpoint repair we speculatively execute instructions that follow an instruction that might (but probably won't) cause an interrupt.  And similar approaches can be used to speculatively execute the instructions that follow a branch instruction.  Prefetching uses extra transistors to fetch data or instructions that might (but won't necessarily) be needed in the future.

Both branch speculation and prefetching are often augmented with even more transistors to predict what intructions/data has the highest probability of being useful in the future.

A third approach for trading off transistors for performance is caching.  A cache is a (usually small and fast) memory used to store the results of expensive work, so that if an identical request is made in the future the result can be returned from the cache rather than by recomputing the result.