Originally, they couldn't license the actual data, either, because at least the road network wasn't Google's to license. It came from TeleAtlas (after Nokia had bought NavTeq), Zenrin for Japan and a few more. Things were tricky like that before the Ground Truth project (https://www.youtube.com/watch?v=FsbLEtS0uls) covered enough of the planet.
When Google launched navigation on Android, it lost money in countries not covered by Ground Truth, which I think was everywhere outside the US. That's because TeleAtlas and co. charged N times as much when the same data was used for real time directions.
This seems better for consumers in the long run: better to have two maps apps on the device, both attempting to be comprehensive and accurate.