It comes from the Paschen's Law.
The following graph is a Paschen curve taken from this research.
The graph may look a bit awkward to make a conclusion as "required clearance increases with altitude."
The horizontal axis represents the distance between the two conductors in open air. Starting from a conductor-to-conductor distance of 0.1 mm and an altitude of up to 50 kft (~15250 m) the effect becomes more pronounced. For example, for a distance (clearance) of 0.2 mm, the breakdown voltage (the voltage enough to generate an arc) is about 2 kV at sea level and drops to 750 V at 10 kft (~3050 m).
A similar curve can be obtained by taking the horizontal axis as air pressure (decreases with altitude) for a constant conductor-to-conductor spacing.
IPC tables also include a correction factor so the numbers shown on the tables may not match to the graph above (or Paschen's experimental results).