I was a bit hasty in my initial posting, and now I realize that there are a few squares near the corners of the reachable area that can actually not be reached. I was also wrongly imagining the shape of the boundary as if the distance between the outermost points was 4 steps (which you would get for a piece that could leap over distances 3 and 4). This does not change the answer for how many steps you need to cover a million squares, though, as this was overshoorting that target by more than 4000 squares. The correct argument is this:

Using oly steps of length 3, a 'diluted grid' with spacing 3 an be reached. The image below shows one quadrant of the reachable area for 5 such moves, the Hawk starting at #, the * indicating reachable squares.

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

# . . * . . * . . * . . * . . *

Next we check how we could get to in-betwee squares. The upper-right corner can only be reached by 5 diagonal leaps of length 3. But by replacing oe of these by a leap of length 2, we advanced one square less along the diagonal ('1' below), and doing that twice even two squares less ('2'). To advance even less along the diagonal (e.g. to 'C'), we can just take fewer steps.

* . . * . . * . . * . . * . . *

. . . . . . . . . . a b c . 1 .

. . . . . . . . . . 2 2 . 2 . .

* . . * . . * . . B 3 x C . c *

. . . . . . . . 1 1 y 1 x 2 b .

. . . . . . . . + + + y 3 2 a .

* . . * . . * . + A + 1 B . . *

. . . . . . . . + + + 1 . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

* . . * . . * . . * . . * . . *

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

# . . * . . * . . * . . * . . *

The diluted-grid squares on the outer rim next to the corner can only be reached by 4 diagonal leaps, followed by one orthogonal one. But this gives us the choice to replace only diagonal leaps by a length of 2 (tracing a diagonal via 'b' and '2' to 'B'), or also replace the orthogonal step by a shorter one (leaving us at 'c'). For any square you can reach you can also reache squares diagonally inward by replacing one of the diagonal leaps by a shorter one. Note that even to go 5 leaps straight up you can always take half the steps diagonally up-right, and the other half diagonally up-left, so there are always many diagonal steps available in the path that you could make shorter.

Note that for reaching squares on the diluted grid two steps inward from the outermost ring (e.g. 'A'), you need two steps less than you have, so you can make the remaining two steps 3-out, 2-in to step, to step to the adjacent squares '+'. This fills up the entire plane in the inner region. Square 'a' can be reached by stepping to 'C', and then take a leap of length 2 perpendicularly.

So all squares just inside the outer periphery are reachable, except those next to the '1'. And for each of those you can move to the squares more diagonally inward. That leaves only the diagonals adjacent to the main diagonal. C can be reached with 3 diagonal leaps, then one up and one right. By taking one of the latter of length 2, we can reached the 'x' squares. (And thus also the squares diagoally inward from those, such as 'y'.) So from the (6*N-1) x (6*N-1) area only 4 x 4 squares near the corners are not reachable.

On the outermost rim only 2*N squares are reachable on each edge (counting the corners as 1/2, because they are on 2 edges). So the total number of squares reachable in N moves is (6*N-1)*(6*N-1) + 8*N - 16. For N=167 this is 1001*1001 + 1336 - 16 = 1,003,321 squares.

Note that this calculation is based on that the number of allowed moves is large, so that you could always find enough steps in the desired directions to replace by a shorter one. For N <= 3 this would not always be possible, and the formula would not apply.