I believe you could say it without the "with," but it would probably be much more common to have it in. If you're comparing two things that overlap, it is standard to explain the other one by setting it off with "with." Whereas, if you're just saying "Two things overlap," it is unnecessary. However, even there, you could say, "The two overlap with each other."
In addition to what Jeff said, there is the question of whether one thing overlaps another "opaquely," eclipsing it so to speak, or "transparently," the way red and yellow overlap to create orange. The preposition with is used with concepts more than concrete objects, because they tend to overlap in a way that "blends."
But physical objects tend to simply overlap. A throwrug covers the passageway between two carpeted rooms, overlapping both carpets. You'd never say the rug overlapped with the carpet because in literal overlapping the accusative concept is appropriate-- one object physically covers the other.
In figurative overlapping, the indirect-object (dative or ablative) logic applies, and the overlapping does something with what is overlapped, usually transform the zone where the overlapping occurs. .
I would definitely not add the with. It sounds very wrong to me. It seems that the consensus is that some people think it is only correct without the with, and others say it could be either way. So if you leave it out, no one thinks it's wrong.