It is all about the loss of energy during each stride - the tendons store some energy, but not a lot. A kangaroo and a greyhound, for example, have far more efficient elastic storage in their legs / tendons, allowing them to achieve (and maintain) greater speeds with less effort. Key phrase from the abstract in that reference:
elastic storage of energy is extremely important to the economy of running gaits
There is a nice demonstration that this is so. Somebody invented pogo stilts which allow an average person to "run" at 20 mph. They don't became stronger when they put these on - they just become more efficient. This means that a larger fraction of the physical "work" done when wearing these is against the air drag - with lower losses in the motion of the muscles.
Note that the problem is not the up/down motion of the center of mass (although that contributes) - it's the fact that muscles have to stretch and contract under tension. When they move in a direction opposite to the force (when they do "negative work"), they don't store the energy. You know this is true - when you try running down a steep slope, it's hard work. But from a physics perspective, work is being done on you... yet you get tired.
By contrast in a bicycle there is just the pushing motion of the muscles ("positive work") - there is virtually no part of the motion where the muscle is pushing against a pedal going the other way (if you use proper technique). At the extreme case, you can roll along on you bicycle without pedaling for quite some time - there is no way to keep going for even a very short distance at walking speed without spending significant effort, since you have to keep moving your legs - and about half of that motion is "contraction".
An interesting article about "form" talks specifically about the issue of footstrike - what part of the foot you land on, and where that lands. It clearly identifies the need to land almost directly below the center of mass of the body - in other words, minimizing the "contraction" part of the stride.
Example of a good footstrike (source - Meb Keflezighi at the Boston Marathon):

and bad footstrike (too far forward)source:

The inefficiency goes as $(1-\cos\theta)$ - that's the amount of movement that has to be absorbed. For small $\theta$ that scales with $\theta^2$, so overstriding quickly becomes a problem. Proponents of barefoot running claim that the padded heels on many modern running shoes are fueling this "bad" style because it doesn't hurt to run badly - you just do a lot of work, and go slowly. And the shocks eventually get to your joints.