They have over 40k locations. Many are 24/7. They also surely churn through employees, have many part time employees, and probably get many more applicants than they hire.
The employees will be hired by the franchisees but they still use the McDonalds software.
Millions is not a surprise to me at all. Perhaps that it's tens of millions is a little surprising, but it still seems within the realm of possibility.