If we assume that the Single Impact Hypothesis regarding the martian dichotomy (wikipedia) and the Giant Impact Hypothesis regarding the Moon's formation (wikipedia) are true, then is it possible that these two events were related?
Here, by related I mean that they were not independent from one another.
Early in the solar system's history, the Sun was surrounded by a protoplanetary disk, full of gas, dust and rock. Eventually, protoplanets began to form. These were small, rocky bodies - smaller than the rocky planets today, but bigger than asteroids. Think of them as dwarf-planet-sized objects. All the terrestrial planets formed from them.
Anyway, as you might know, the object that slammed into the Earth (according to the GIH) was one such protoplanet, lovingly named Theia. The resulting debris coalesced into the Moon. The SIH tells of a similar story: Once again, a protoplanet headed on a collision course, this time towards Mars. It slammed into Mars, creating a large basin. Simple but effective.
There's one thing that can relate these two disaster tales together, and that is the protoplanetary disk. Remember, the protoplanets formed from the same disk. The differences in them stemmed from the materials they formed from. So we could relate the two suicidal protoplanets to each other via that connection. Also, most collisions in the inner solar system were due to the erratic orbits of these protoplanets, so it is likely that the fault for the collisions lies solely on the protoplanets.
I think you want something a bit different from random collisions, though; the previous reason is a bit of a cop-out. Well, there is something more interesting: the rocky planets weren't alone in the early solar system. There were still their big siblings: the gas giants. The gas giants hadn't yet grown to their full sizes, but their cores and early atmospheres were still pretty massive, and commanded a strong presence in the outer solar system. It is possible that the two objects that hit the Earth and Mars formed together farther away from the inner planets, and were gravitationally perturbed by the gas giants, swinging in from an outer orbit towards the inner solar system.
You might have heard of the Nice Model. Basically, this says that the gas giants formed closed to the inner solar system than they are now. They encountered some of these early protoplanets and flung them into the inner solar system, moving outwards in the process. thus, collisions increased in the inner solar system.
It's a "nice" explanation. Trouble is, the majority of this "flinging" happened later on in the solar system's history; it has been suggested that the gas giants did this and thus caused the Late Heavy Bombardment. Still this idea shows that there could have been interaction between the protoplanets and the gas giants.
So how does this relate the two suicidal protoplanets? Well, it means that they could have formed together, further out in the solar system, and have been brought in by a gas giant. They could even have been part of a larger object, which broke apart after various collisions. But if the two objects had formed together (even somewhere in the inner solar system), or been part of a larger object, they should be made of the same materials, right? So if we were to travel to Mars we should be able to find similar materials as we did on the Moon. So far there hasn't been much luck along that avenue, but the search will continue.
To summarize: The early solar system was chaotic. It is likely that the impacts were unrelated, and that the two suicidal protoplanets formed apart in the inner solar system, but they could have formed together further our and been perturbed by one of the gas giants. They may or may not have been formed neary each other, or even been fragments of the same object. Detailed analysis in the future could give us some clues as to their formation.
