The existence of possible early oceans in the northern hemisphere of Mars has been researched and debated for decades. The nature of the early martian climate is still somewhat mysterious, but evidence for one or more early oceans implies long-lasting periods of habitability. The primary evidence supporting early oceans is a set of proposed remnant shorelines circling large fractions of the planet. The features are thought to be older than 3.6 Ga and possibly as old as 4 Ga, which would make them some of the oldest large-scale features still identifiable on the surface of Mars. One question that has not been thoroughly addressed, however, is whether shorelines this old could survive modification and destruction processes like impact craters, tectonics, volcanism, and hydrology in recognizable form. Here we address one of these processes -- impact cratering -- in detail. We use standard crater counting age models to generate synthetic, global populations of craters and intersect them with hypothetical shorelines, tracking portions of the shoreline that are directly impacted. The oldest shorelines (>= 4 Ga) are at least 70 % destroyed by direct impacts. Shorelines of any age >3.6 Ga are dissected into relatively short, discontinuous segments no larger than about 40 km when including the effects of craters larger than 100 m in radius. When craters smaller than 500 m in radius are excluded, surviving segment lengths can be as large as ~1000 km. The oldest shorelines exhibit fractal structure after impacts, presenting as a discontinuous collection of lines over a range of scales. If the features are truly shorelines, high-resolution studies should find similar levels of destruction and discontinuity. However, our results indicate that observing shorelines as old as 4 Ga, should they exist, is a significant challenge and raises questions about prior mapping efforts.