You have to assume a characteristic mass for the stars in the cluster. Usually, to get an approximate I go with stars of mass $1 M_\odot$.
Then, given the density of $10^6\ M_\odot.\mathrm{pc}^{-3}$ you have a density of stars of $\rho_\star = 10^6\ \mathrm{pc}^{-3}$. In a box of $1\ \mathrm{pc}^{3}$, you have $10^6$ stars, so the characteristic distance between stars is simply given by the density of stars to the minus one third:
$$ d_\mathrm{carac} = \rho_\star^{-1/3} \approx 10^{-2}\ \mathrm{pc} \approx 2000\ \mathrm{AU}.$$
Addendum: if you want to do a more correct calculation, you should take into account the different masses of stars to estimate the correct number of stars, using for example a Chabrier initial mass function and try to get the mass function at the age of the cluster. Because of the fact that stars of about $\geq 1 M_\odot$ reach their red giant branch and lose much of their material in less than the age of the cluster, it will decrease the mean star mass of the cluster to something between $0.1$ and $0.8 M_\odot$ ($0.3 M_\odot$ according to Rob Jeffries). However it won't change the order of magnitude of the mean distance between stars.