I'm sure the gains from AdSense and Gmail alone outweigh anything they lost. Also engineers can stay happy if they work on things they like more often. So there could be an implied cost (by losing employees) to not allowing 20% time. I'll also add that it's almost impossible to stay focus on 1 thing 8 hours+ a day for 5 days a week. Even if there is no 20% time I'm sure they still lose time to unproductive activities. Maybe 20% time actually captured some of the time that would otherwise be spent browsing the web or making pointless comments like this on HN.
Failure is a prerequisite for success, though. As long as those failures were inspected, digested, and understood, then the company gained more in terms of training than they lost in operational costs.
What is your definition of "failure?" A project that nobody uses and makes the company no money is a failure in terms of direct profitability, but may be a success for other reasons. Your engineers get to exercise their minds in unusual ways and keep themselves sharp. Your engineers are more willing to put up with boring tasks. You attract talented people who want to be self directed at some level.