Seriously, I consider this to be Microsoft's key innovation: the idea that people should pay for software and that people should be forced to pay for software.
What Microsoft actually did was make deals with OEMs and distributors so they got paid for every machine sold. In the 1980s, home computers had MS-BASIC in the ROMs, and PCs came with "Vendor DOS", you couldn't even buy MS-DOS.
The payment for software was well established on big iron by the 1970s before Microsoft were established