Sound is a hydrodynamic effect. To be in a hydrodynamic regime, the wave length of the sound must be large compared to the mean free path of the air molecules. As the density of the air goes down and the inter-particle spacing grows, there is a very real effect that the minimum wave lengths of sound one can consider grow accordingly.
The sound speed squared is given by $(\partial p / \partial \rho)_s$ where $p$ is the pressure, $\rho$ the mass density, and $s$ the entropy. The $s$ outside the parentheses means that entropy should be held constant in taking the derivative. At a first pass, we can ignore this constraint, and just do some dimensional analysis using the ideal gas law, $pV = n R T$, where we can identify $\rho = n M/ V$ where $M$ is the mass of a gas molecule. Roughly then, $(\partial p / \partial \rho)$ is proportional to $T / M$. The density drops out. Of course, we performed this derivative at constant $T$, not constant $s$. Fixing this up will introduce a factor of $\gamma$, the adiabatic index, an order one number which depends on the structure of the gas molecule -- monatomic, diatomic, etc. The density, though, drops out of the sound speed. More details can be found here.
