I know kind of a very elementary method to factor this number. Consider the following: $$10^6-1 = (10^3-1)(10^3+1)=9 \times 11 \times (10^2+10+1)(10^2-10+1) = 9 \times 11 \times 111\times 91$$ I would then factor each number individually.
Is there a faster method? The great hint is that this number is a rep unit number = $9\ \times 111111$.
On
\begin{align} 10^6 - 1 &= 1000000-1\\ &= 999999 \\ &= 3^2 \times 111111 \\ &= 3^2 \times 111\times 1001 \\ &= 3^2 \times 111 \times (1100 - 99)\\ &= 3^2 \times 111 \times 11 \times (100-9)\\ &= 3^2 \times 111 \times 11 \times 91 \\ &= 3^2 \times (3 \times 37)\times 11 \times 7 \times 13 \end{align}
On
If you have a computer, you could use this idea for an algorithm to factor:$$10^n -1 \equiv 0 \mod p \iff 10^n \equiv 1 \mod p$$ This will be more feasible for large values of $n$ because most programming languages have an efficient modular exponentiation function that already exists. If a prime $p$ satisfies this equivalence, it's a prime factor, though you will have to run additional trials to find the degree of $p$.
You have gotten as far as the difference of sixth powers will take you. Now $111$ is divisible by $3$ by the sum of digits test, you know $9=3^2,$ and you are down to $3^3\cdot 11 \cdot 37 \cdot 91$. I don't see anything better than trial division at this point. For $37$ you only need to go up to $5$ to see it is prime. For $91$ you need to go to $7,$ you find $91=7\cdot 13$ and you are done. Maybe you know the last two off the top of your head.