All the leeway you want, basically, with one caveat. With an original close to 4 MHz clock, the lowest possible frequency (because of hardware limitations) corresponds to about C-3. No problem. With a close to 2 MHz crystal, it would instead be C-2, which is just one octave below. (Often done to gain an extra octave of bass.) Also no problem.
If you put in say a 3 MHz crystal, the lowest frequency would be something G-2. You now have a couple of options. Make the scale start at G-2. Map everything to their true notes starting at C-3, and ignore the newly available half octave below C-3. Map everything to their true notes starting at C-2, but map C-2 to F#2 (or so) to the frequencies one octave above. It can be a bit extra tricky, but anything is possible, really.
Things to keep in mind though, too low clock frequency, LSDj or other software may run too slowly to play your song without lagging. Too high frequency, and you put a limit on how low notes you can play, and also, there's some limit on how hgh frequencies the CPU can tolerate.