Solution:
The numbers arrange themselves in squares. For example, 4 is in the top-left of a square containing the numbers 1-4, while 16 is in the top-left of a square containing 1-16, etc. There is a pattern of even square numbers going up and to the left, so because 1,000,000=1000^2, it is in the top left of a square containing the numbers 1-1,000,000.
That means that directly to the right of it, there will be the number 999,999, and directly to the left will be the number 1,000,001. That is when the pattern turns down, so below that is 1,000,002 (which is down-left from 1,000,000). So we've found three of the numbers around 1,000,000.
Down and to the right of 1,000,000, there will be the number 998^2=996,004 because another square finishes there. To the left of that (and right below 1,000,000) is 996,005.
Up and to the left of 1,000,000 is 1002^2=1,004,004. To the right of that (and directly above 1,000,000) is 1,004,003. To the right of that (and above-right of 1,000,000) is 1,004,002.
Thus, the eight numbers near 1,000,000 are 996,004, 996,005, 1,000,002, 999,999, 1,000,001, 1,004,002, 1,004,003, and 1,004,004.
Now, for the extra bonus. The number 1,000,010 appears nine spaces below 1,000,001 along the side of the square. Directly to the right of it is the number that is eight spaces below 996,005, which is 996,013. Directly to the left of it is the number that is ten spaces below 1,004,005, which is 1,004,015.
Above and below 1,000,010 are 1,000,009 and 1,000,011. Above and below 996,013 are 996,012 and 996,014. Above and below 1,004,015 are 1,004,014 and 1,004,016.
Thus, the eight numbers near 1,000,010 are 996,014, 1,000,011, 1,004,016, 996,013, 1,004,015, 996,012, 1,000,009, and 1,004,014.