How the Himalayas were made
Mountain formation isn't the best known process in the world. The general process for the formation of the Himalayas is described in Wikipedia, as are the various disagreements on the pre-Himalayan geology.
The general subject for disagreement is which parts of the Indian and Eurasian plates along with the Tethys seabed ended up where. Le Fort, 1975 extensively documents the known (in 1975) ages of deposits in various parts of the Himalaya. The general facts are, and this is well illustrated by Fig. 2 from the paper on page 4, that there are some regions of the Himalaya where surface deposits are Triassic in origin (200-250 mya), while other areas such as Kumaun district of Uttarakhand state have deep Eocene marine sediments as young as 40 mya.
These deposit ages are relevant as they determine the actual timeline for how long the Himalayas took to form. India started colliding with Eurasia around 55 mya, and the aforementioned marine sediments were deposited on the bottom of the Tethys Sea as recently as 40 mya, indicating that what is currently the Himalayas definitely did not exist as of that time. Page 15 of Le Fort shows evidence for a terrestrial coastal environment as recently as 26 mya, an analysis echoed in Najman, et al., 1997.
The timeline suggested in Tapponnier, et al., 2001, graphically described in Fig 3., page 1674, suggests that there was an initial period of mountain building starting with the Bangong suture up to 120 mya. This was caused by a India ripping a piece of Africa off when it separated from Gondwana. This detached crust piece was the Lhasa terrane, which was pushed pushed by India into Eurasia and built the first piece of the Tibetan Plateau. This collision formed a volcanic region called the Gangdese batholith.
After this collision, there was still the Tethys sea between India and Eurasia; the Lhasa terrane was separated from India by oceanic crust. It took tens of millions of years to close what was left of the Tethys sea. The rest of the continent of India didn't start to collide with Eurasia until about 55 mya. This collision re-ignited the Gangdese volcanic belt and causing the Jinsha suture to rise from from 50-20 mya. This phase of the collision probably coincided with volcanic mountain building of the same sort that made the Andes and Cascades in the Americas. A detailed (and very readable for a paper, in my opinion) description of this phase is in Jain, 2014.
Finally, about 25 mya, the subduction could no longer continue smoothly and a massive thust-fold belt formed what is now the Himalayas. The previous volcanic mountains are now part of the sub-ranges of Tibet such as Nyenchen Tanglha Shan. Sorkhabi and Stump, 1993 argue from isotropic evidence of changing fluvial (river) patterns, that there were three major pulses of uplift, between 21-17 mya, 11-7 mya, and starting 2mya to present. This is summarized on page 89-90 of their paper. During those times (and indeed during the present) the mountains would have risen at rapid rates.
Over at Earth Science SE, there are a few posts talking about maximum possible heights of mountain ranges. Without going too much into detail, the Himalayas are probably about as tall as mountains can possibly get; since at about 8000-9000m, erosion rate from glaciation starts to exceed maximum possible uplift. So the conclusion from Sorkhabi and Stump is that for those three pulses, including the one at present, the Himalayas were about as tall as they are now.
Conclusion: How fast can they rise
The available evidence suggests that the material that currently makes up the Himalayas was a coastal plain as recently as 25 mya. By 21 mya it was being uplifted at a rate that caused its height to be capped by erosion at about the height we see today. So we are looking at 4 million years to form these mountains from 'nothing.'
However, this does come with caveats. The Himalayas didn't form from 'nothing' but from a foreland basin, that was 'sunk' between the higher elevation Indian shield and behind it and the Tibetan Plateau, which had already existed for 75 million years in front of it. The Tibetan Plateau, in particular, was already pretty high, and had ranges of volcanic activity that had built mountains there for the past 40 million years.
An analogy to the situation in today's world would be this. The Persian Gulf and Mesopotamia is a foreland basin between the Iranian Plateau in front of it, and Arabia behind. The Gulf could (if the plates were lined up just right) rise into Himalaya-sized mountains in 4 million years. However, there would already have been a significant mountain range in the area before this 4 million year orogeny started; they just wouldn't seem so significant once there were 8000m peaks towering over their southern border.
Final TL;DR conclusion: Himalaya-size mountains could form in as little as 4 million years from a shallow sea, but there would already have been volcanic mountains from the subduction zone in the area for tens of millions of years.