Well to answer your questions briefly: we can't.
How it should be: McDonald doesn't want to run a business which will end as a financial ruin they will try there best to fulfill the laws of a country. And the authorities in such a country who will permit McDonald to run a fast-food restaurant have to be on the side of their citizens and check if the presented food is good/halal for them right?
Therefore if McDonald run a fast-food restaurant and pretend to serve halal food and the authorities don't check the food or the origin of the food (in this case). It's not the customer who made a sin, so if he eats something there in good faith that the authorities did their job he won't be the one to be accused. The other possibility would be that the authorities provide the meat/food or the suppliers for McDonald to avoid non halal meat/food!
How it might be: I guess (and maybe i'm wrong) in most Islamic countries we don't have any regulatory agency or authority who checks the food. As for example i heard in Radio that Casablanca (Morocco) the official slaughterhouse can't afford the need of the local market many butchers slaughter in nonofficial abatoirs! And in many rural regions you won't find public authorities! My experience as a tourist in Egypt taught me it's better to eat at McDonalds or KFC than at al-Mu'min as we found some spoiled Seafood in our sandwich! So i hope i don't go to far if i said maybe McDonald as a global player will satisfy it's part rather than the local authorities (But Allah knows best)!
I've lately seen a commercial of McDonalds in Morocco, where they claim that the meat is halal!
Of course what you mentioned by saying "How can they be there saying bismillah and reciting a prayer every animal they slaughter when they kill millions of them." is hard to check!
There are some kind of workarounds:as muslims we have an option to say bismillah and allahu akbar before eating the food this should be a minimum assurance for making it halal, as some scholar (espacially from al-Azhar) allow us to eat the food (=meat expect porc and alcohol free) prepared by people of the book (jews and christians) by saying this. As we know that surat al-Maida is one of the last revealed and we find in it Quran (5:5)
"All the good and pure things have today been made lawful for you; the
food of the people of the Book is lawful for you, and your food for
them, Likewise you are permitted to marry chaste believing women or
chaste women from among the people who were given the Scripture before
you provided that you give them their dowries and become their
protectors in wedlock; this permission is not for sensual license or
secret illicit relations; whoever rejects the way of Faith, all the
deeds of his life shall become vain and he shall be a bankrupt in the
Hereafter"
And Allah knows best!