Atmega8 input impedance
Look in the datasheet and find the pin leakage current.  CMOS digital inputs are usually specified as having a maximum leakage current as apposed to a minimum resistance.  Now look at the minimum guaranteed logic high input voltage at your operating conditions.  The supply voltage minus the minimum high voltage tells you the maximum voltage the pullup can drop and the input to still be interpreted as high.  That drop voltage divided by the total leakage current is the maximum theoretical allowed pullup resistor.

Note that I said "total" leakage current.  This is not only the pin input leakage but leakage from all other sources, like other pins of other devices connected to that node, whatever you think the leakage is accross the PC board at the worst case level of dirt and humidity, etc.  In practise you can't know all these things.  Do all the calculations you want, but I'd want a pullup at least a order of magnitude lower resistance than the maximum theoretical you calculate.  When current consumption matters, I usually figure 100 k&Omega; is the maximum safe and reliable value.  When it doesn't, I'll use 10 k&Omega; unless there is a good reason not to.