Why did the Z80 with 4-bit ALU out-perform the fully 8-bit Intel 8080?
Did it? I guess this depends on what 'performance' meant here.
If it's about instructions per clock, then No. They are, for all practical purposes, identical.
If it's about reaching higher clock speed, then Yes.
If it's about an increased instruction set, then as well Yes.
If it's about sales, then at best a Maybe.
If it's about usage in cheap home computers, then most definitely Yes.
So, I guess it would help to know what should be considered 'out-performing'.
Looking at the development and architecture of the Z80, it appears to be a scaled-down, cost-reduced, clone of the Intel 8080.
True. That and a greatly improved interrupt handling - like the majority of microprocessors at the time it was designed for embedded application; having the fastest interrupt handling at the time, combined with full code (and large hardware) compatibility and optional higher clock speed was a killer USP.
It only used a 4-bit ALU. I assume this would have reduced its performance considerably.
That's the fun part, as it doesn't. Using a half-sized ALU, while staying within the 8080 timing is another optimization. This was possible as Frederico Faggin figured out a way to stay within 8080 timing (which he had to do) but saving on half the ALU.
Changing ('improving') instruction timing was neither a goal, nor would it have been of any help, as it would not have resulted in any speed improvement. At least not without requiring faster memory as well. A no-go when intending to build a cheaper chip.
However, the Z80 out performed the Intel version and
Again, this needs a definition of what out-performing should mean.
nearly displaced it completely in the CP/M market.
True. But while the CP/M market is quite visible, it was always only a tiny fraction of the CPU market. The true market in which Intel and Zilog were competing was about embedded systems, were Intel had a very strong hold.
Also, the dominance of the Z80 here was due less to higher performance, but rather to lower cost. The chip itself was lower priced than Intel's 8080/85 and it needed fewer support chips. Both were very important factors in the extremely cost-sensitive market of small/home computers. For embedded, both factors play a lesser role. Here, not only are the margins way higher, but also long term-supply reliability defines products - a card Intel played quite well until 486 times.
How did Zilog design their ALU to both out-perform and save cost?
The ALU did not out-perform: instructions executed equally fast. This saved money due to lower production cost. It's also important to keep in mind that halving the ALU was just a tiny part of savings.
Bottom line: It was all that was needed to stay on par with the 8080.
Clarification: Put slightly differently, the Z80 performs 8080-alike operations in the same number of cycles whilst having an ALU that operates on half as many bits per cycle. How?
Essentially by using a 4 bit wide (on entry) deep pipeline, aka a set of two 4-bit latches. Ken Shirriff did a good writeup of the internal structure of the ALU and how it's integrated. There is also a great answer on Electronics.SE.