Because $2^{10} = 1024,$ and $1000^2 = 1,000,000,$ we can see that $(2^{10})^2 = 1024^2$ which is obviously greater than $1,000,000.$
If we have $2^{19},$ that is $2^10 \cdot 2^9 = 1024 \cdot 512$ which is obviously less than $1,000,000.$
Thus, $2^{19} < 1,000,000 < 2^{20}$
Note $8^{n} = 2^{3n}.$
Since we know that $2^{19} < 1,000,000$ and $2^{3n} < 1,000,000, n = \left \lfloor{\frac{19}{3}}\right \rfloor = 6.$
Thus, $8^6 < 1,000,000 < 8^7.$
We have the answer to be $19 - 6 = \boxed{13}$
.