You know that old joke that, if you and a halfling are chased by an angry dragon, you don't have to run quicker than the dragon, you only have to be quicker than the halfling? Assuming non-malicious users*, you don't have to restrict their access to the public cloud, it is enough to make the usability of the public cloud lower than the usability of whatever enterprisey solution you have for non-desk-bound data access. Properly implemented, this will reduce the risk of non-malicious leaks sharply, and is doable with a fraction of the cost.
In most cases, a simple blacklist should suffice. Put Google drive, Dropbox and the Apple cloud on it. Also block traffic to Amazon AWS - most of these hot startups who build yet another cloud service don't build their own data center. You just reduced the number of employees who know how to get into the public cloud from 90% to 15% (very rough numbers, will differ by industry). Use a suitable error message to explain why public clouds are forbidden, which will reduce their impression of wanton censorship (sadly, there will always be users not willing to understand).
The remaining 15% can still reach providers not on the blacklist, but they probably won't bother to do it. Google drive and co are subject to strong positive network effects (the economic kind, not the technical kind). Everybody uses the same 2-3 services, so they get built in everywhere. Users build convenient, streamlined workflows which include these services. If the alternative cloud provider cannot be integrated into such a workflow, the users have no incentive to use it. And I hope that you have a corporate solution for the most basic usage of a cloud such as storing files in a central place, reachable from a physical location outside of the campus (with VPN if security is needed).
Add to this solution a good deal of measurement and analytics. (This is always needed where users are concerned). Take samples of traffic, especially if exhibiting suspicious patterns (upstream traffic in bursts large enough to be upload of documents, directed at the same domain). Have a human look at the identified suspicious domains, and if you find that it is a cloud provider, find out why users are using it, talk with management about providing an alternative with equal usability, educate the offending user about the alternative. It would be great if your corporate culture allows you to gently reeducate caught users without implementing disciplinary measures the first times - then they will not be trying to hide from you especially hard, and you will be able to easily catch deviations and deal with the situation in a way which reduces the security risk but still allows the user to do his job efficiently.
A reasonable manager** will understand that this blacklist will lead to productivity losses. The users had a reason to use the public cloud - they are incentivized to be productive, and the convenient workflow increased their productivity (including the amount of unpaid overtime they are willing to do). It is a manager's job to evaluate the trade off between productivity loss and security risks and tell you if they are willing to let the situation as-is, to implement the black list, or to go for secret-service-worthy measures (which are severely inconvenient and still don't provide 100% security).
[*] I know that people whose job is security think of criminal intent first. And indeed, a determined criminal is much harder to stop and can inflict much worse damage than a non-malicious user. But in reality, there are few organisations which get infiltrated. Most security problems are related to the goofiness of well-meaning users who don't realize the consequences of their actions. And because there are so many of them, the threat they pose should be taken as seriously as the more dangerous, but much rarer, spy.
[**] I am aware that, if your bosses already made that demand, chances are that they are not the reasonable type. If they are reasonable but just misguided, that's great. If they are unreasonable and stubborn, this is unfortunate, but you must find a way to negotiate with them. Offering such a partial solution, even if you can't get them to accept it, can be a good strategic move - properly presented, it shows them that you are "on their side", take their concerns seriously, and are prepared to search for alternatives to technically infeasible requirements.