I'm gonna say the original premise of this thread is to idealize a situation where Alexander embarks on an invasion of China, not force him into it at the extremity of his logistical supply line with a relatively small, exhausted army in mutiny, which kills the whole point of the discussion.
So sticking with logical events, instead of drinking himself to death while he's sick with malaria, he does consolidate his empire, picking up the coastal states of Arabia, and launching his land/sea campaign against Carthage, winning the allegiance of the western Greeks. He uses his experience and the example of his father when he marches through the territory of the Gauls and Celt-Iberians, or the lower Danube, winning some over by sword and persuasion. He is about to avenge the death of his uncle at Pandosia, in Italy.
By this time he is probably 10 years older, but I will point out that his veterans of the Macedonian conquest were vaunted prizefighters in the Wars of the Diadochi for more than 10 years after his death. (They would have been experience level 5 or higher in Civ4 terms). Rome and Samnium would have put aside their multi-generational war and presented a formidable opponent. However, the fact that Pyrrhus fought Rome to a draw 50 years years later, and Alexander holds mastery of the sea, with a highly professional army supplemented by specialist corps from every major culture of the Mediterranean Basin (much like the Thessalians, Thracians, Illyrians, etc. were integrated in Philip's army), leaves little doubt as to the outcome.
Now he's ready to turn back to the east, even if some of the western Mediterranean is only nominally held in his name, the core of his empire is safe, and his reputation even more legendary. He's probably pushing 50 now, and assuming he is still whole after the hard living that killed him when he was 33, most of his elite core are either dead or allowed to retire, but they've raised a new generation army trained in the same traditions, with the most experienced officers in the world. I'll also point out, that Alexander's generals fought eachother in the wars of the Diadochi until they were 80+ years old.
What keeps him moving quickly is Alexander doesn't bother stripping his frontiers of militia and reserve troops, or calling a general levy, and that's not his style anyway. His reputation and direct command is enough to ensure the best troops are at his beck and call when he announces another expedition to the east, this time to reach the Ocean. By this time he's received enough intelligence to realize the far shore is not on the other side of India, other great fabled lands lie farther to the east. I would estimate 100,000 to 150,000 men, mostly veterans, accompany him into Asia, while a fleet sets sail from the Persian Gulf. Any wavering allegiance in this part of the world is quickly restored, and Alexander gathers large numbers of middle eastern horsemen and skirmishers, along with the siege expertise of Greek subordinates and sons of subordinates like who would be Demetrius Poliorcetes.
The big question is whether he goes after India first. The Mauryan Empire founded by Chandragupta I is very powerful, but he had been quite impressed by Alexander on his first visit - I think he would have offered some kind of allegiance or submission. If not, then Alexander's last great conquest would be the Indian sub-continent, much like the Greco-Bactrians did a century later. With the aid of a fleet, I have little doubt he would succeed, but this would consume his Asian expedition, and he would get hopelessly bogged down crossing the successive mountain ranges and rivers of Burma, jungles of SE Asia, just to reach the rugged southern doorstep of China, as an earlier poster suggested. But why would anyone choose to go that way ?
If India can be pacified and/or left to a subordinate ally, Alexander gathers his army in Baktra, the largest concentration of Greeks east of the Tigris, which happens to sit near the entrance to western China through the Tarim Basin. In typical Greek fashion, Alexander leaves a third of his prize army behind under a trusted general to guard his back, with orders to follow with a supply train in 2 or 3 years if the situation is stable, or when he sends word. He would be in an extremely precarious position so far from his center of power, to leave his hinge of departure unguarded. When he moves out let's assume he has a core army of 120,000 infantry with the medium-heavy cavalry, siege and supply train, plus a scouting force of 40,000 light cavalry from his Asian allies, without overstretching the logistical resources of his vast empire.
He may have to deal with Scythian and Ugric tribesmen first, who are hard to bring to battle. It is also probable that word of this would precede him and some of the Chinese states would prepare a reception for him. As in history, European armies of the day were usually ill-suited to warfare on the open steppes, but he would have some experience of that from his Asian conquests, and quite likely include a few hundred war elephants in his inventory that tended to cause panic among enemy horses. Furthermore, this is not the Han Dynasty of a hundred years later when they actually took the offensive successfully against the Hsing-Nu and other steppe nomads. This is the Warring States period, and quite certainly he would take advantage of their division to form an alliance with at least some disaffected states.
If Alexander follows the old Silk Road along the oases and river valleys in Sinkiang, there are few natural bottlenecks that will hold him up for long. What happens next I think depends largely on how an outsider like Alexander is perceived within China. As a cruel 'barbarian', the resistance, even of poorly armed and trained militia, might be fanatical or even suicidal. As an enlightened warlord-emperor, which comparatively speaking Alexander was, he may quickly establish a reputation with a few successful battles. I doubt that a scorched earth policy would be uniformly prosecuted, most of China was too populous to sustain such a practice, depending on multiple harvests a year. Once he has the Tarim Basin/Sinkiang region he could pick his enemies and objectives before crossing the last stretch of desert along the Nanshan Mountains to China proper. Rivers flow here in most seasons and nowhere would he have to go for a long stretch without water.
It's a very interesting scenario to hypothesize on - because I could see someone like Alexander actually attempting this. I'm not necessarily impressed that 2 or 3 of the Chinese states might present an army of 3-400,000 to Alexander's advance, unless they were forced to fight to the death by the enforcement of royal decree, or by having no avenue of retreat. Logistics works both ways and such forces could not be sustained in the field indefinitely. But at least a third of them would be a hard-core trained elite, equivalent in size to Alexander's. From reading a bit of the Warring States period, some of their generals employed quite subtle methods as alluded to in the Art of War, and there was no lack of experience in China at this time. Any attempt by Alexander's fleet to explore and find a way to support him in China would be inconsequential. I can see it hopping along both coasts of India for awhile before being scattered by a monsoon, or swarmed by sampans and junks in SE Asia. Unless Alexander knew how to build galleons I can't see a galley based fleet, even with some sailing capability, being of much help (maybe some Arab dhows).
I've set the scenario up now someone else can finish it. I don't think the chariots (heavy war carts) of the Chinese would be very effective against the phalanx, which could leave open gaps for them to be channeled through, or stand their ground with 21' pikes. If the Chinese had large numbers of light horsemen I think they are a bigger threat in harassing his march and cutting him off from supplies. Much is made of the Chinese crossbowmen, but the repeating Cho-ko-nu is not the same crossbow that appeared in Europe 1500 years later, with 150+ lb. draw capable of piercing plate steel. I would point out that even such crossbowmen as the Genoese were only effective to about 150 yards with fairly flat trajectories, and were annihilated any time they encountered longbows with their longer trajectories, but the Cho-ko-nu could achieve a reasonably high rate of fire in support or defense of an infantry assault. Alexander may have some early Indian equivalent longbowmen, and many composite archers, but he had also mastered the use of light skirmishers with shields in open formation, who could close the range quickly and release high volumes of missile fire from javelins and slings before withdrawing.
Finally there is Alexander himself, and his ability to adapt to any tactical situation. By this time he wouldn't be in the front line getting himself killed, therefore I think it is plausible that he would succeed in establishing a protectorate over a part of China, and perhaps enter into the balance of power with the other 5-7 leading states. I don't think he would succeed in conquering all of China - the Warring States period proves just how difficult that was. It would have been the first real encounter between east and west and may have left a closer cultural tie, instead of the isolationism that was finally broken by the Opium Wars, a far less worthy impression in the west's first significant military encounter with China.