Amphitheater-shaped canyons on Earth and Mars have horseshoe-shaped heads, steep sidewalls, and roughly uniform widths over their entire length. On Earth, they may form in loose sediment from groundwater seepage erosion, or in more competent lithologies by waterfall erosion during overland flow. Because canyons record hydrological events and are readily observable from orbital imagery, they constitute prime targets for paleohydraulic reconstructions. However, because their planform morphology is not diagnostic of how they formed, there is a need for new mechanistic theory to identify canyon-formation mechanism. In particular, significant progress can be made in the field of planetary paleohydraulics by combining "classical" open-channel hydraulic laws with erosion mechanics. To this end, we developed a new semi-empirical theory for flow over horseshoe-shaped waterfalls, and applied it to reconstruct the water discharge and duration of floods that carved canyons on both Earth and Mars.