For a bipolar 555, I like to keep the resistors below 5meg, and use larger capacitors.
For a NE555, TI says keep the sum of the two resistors below 10meg. For a LM555, National says 20meg. The issue is that for an astable, the resistor has to supply the input leakage/bias current for TWO pins at once.
If your relay coil draws less than ~200mA, you can drive it directly from the 555 (either way). If it draws more, you will have to add a transistor or Fet or buy a more sensitive relay.