In this scene, Illidan flies from ground level in the Black Temple to above the clouds in 2 seconds.
At this scene you can see what looks like the mountains of Shadowmoon Valley in the background, which makes logical sense considering Illidan's fortress is the Black Temple, in Shadowmoon Valley.
However, here, you can see the clouds.
These clouds appear similar to be Stratocumulus Clouds, which hang around ten thousand feet
However, i will include a low end, with those being the lowest hanging clouds we know, Nimbostratus and a high end, being Stratocumulus, and a what-if, if Illidan ascended above all cloud levels.
Low End: Nimbostratus clouds tops hang around 1000 meters, this translates to 500 meters a second, or Mach 1.4, solid Supersonic. Consistent with bullet-dodging.
High End: Stratocumulus cloud tops hang around 3500 meters. This translates to 1750 meters a second, or Mach 5.1, Hypersonic.
What If: Cirrcus Clouds tops hang around 13500 meters. This translates to 6750 meters per second, or Mach 19. Hypersonic+
I would recommend the High End.
Considering that Illidan is Mid Tier, with High Tiers having MHS and MHS+ feats, this is consistent.