Waves can be coherent and yet not have the same wavelength. It is sufficient that they have the same frequency - because that is sufficient to imply a constant phase difference.
If you make a Michelson interferometer where you split an incoming light beam into two arms, and you send half the light through a column of water and the other half through air, then it is possible to get interference between the beams by adjusting the path lengths (according to the refractive index).
It is worth noting that typically waves do not consist of a single pure frequency, and that there will be some small drift in frequency over time. Because of this, if you split light into two branches but make them come back together after they have covered different path lengths, then the interference pattern they will create (a measure of the coherence) will become less.
For this reason, with "monochromatic" light we sometimes talk of the "coherence length" - a measure of how different the path lengths can be before you lose a significant fraction of the coherence (before the interference pattern starts to fade). As @wbeaty pointed out, it is more proper to call this the temporal coherence length (how much earlier or later can you look at the beam and find it is still capable of interference) - but since you are measuring time "along the beam", there is a direct relationship between the coherence time and the length along the beam that the light can interfere.