They definitely wouldn't turn a blind eye to an OEM distributing them illegally, though. OEMs shipping Android phones pay Google licensing for the Play Store, Gmail app, etc. From what I understand, most Android OEMs also pay Microsoft royalties per handset.

In other words, these are definitely not free to the end user, the cost is just incorporated into the overall price of the phone.