Arduino Nano: How to decide voltage divider values that are safe for the input of the ADC
There are two things to consider:


The ratio of values
The input impedance of the ADC


Point 1 has hard and fast formulae. No rule of thumb here.

Point 2 is a little more "thumby". You want R2 (the lower resistor) to be low enough that the input impedance of the ADC doesn't skew the readings much, yet large enough that you dont get excessive current draw through the divider. As a rule of thumb I work to a 10% rule. R2 should be no more than 10% of the input impedance. That means for an ADC with 1M input impedance you are looking at an absolute maximum of 100K for R2. Anything more and you start to see bad drift. Better is to go lower, but you don't want to go too low. 10K is a good value. Only 1% of the input impedance yet high enough to not waste current.

TO get more specific refer to the datasgeet.

The ADC on the ATMega328P is:


  ... optimized for analog signals with an output impedance of approximately 10 kΩ or less. If such a source is used, the sampling time will be negligible. 


The output impedance of a voltage divider is basically the two resistors in parallel \$(\frac{R1 \times R2}{R1 + R2})\$, but if R2 is considerably smaller than R1 then it will be approximately R2, so about 10KΩ is the maximum the ADC likes to have as R2, though it can be higher if R1 allows the impedance to drop to 10KΩ.

For instance, if you have your example of 1MΩ / 10KΩ, the impedance is \$\frac{10,000,000 \times 10,000}{10,000,000 + 10,000} = 9990\Omega\$ which is about right for the ADC.