We describe and execute a novel approach to observationally estimate the lifetimes of giant molecular clouds (GMCs). We focus on the cloud population between the two main spiral arms in M51 (the inter-arm region) where cloud destruction via shear and star formation feedback dominates over formation processes. By monitoring the change in GMC number densities and properties from one side of the inter-arm to the other, we estimate the lifetime as a fraction of the inter-arm travel time. We find that GMC lifetimes in M51s inter-arm are finite and short, 20 to 30 Myr. Such short lifetimes suggest that cloud evolution is influenced by environment, in which processes can disrupt GMCs after a few free-fall times. Over most of the region under investigation shear appears to regulate the lifetime. As the shear timescale increases with galactocentric radius, we expect cloud destruction to switch primarily to star formation feedback at larger radii. We identify a transition from shear- to feedback-dominated disruption through a change in the behavior of the GMC number density. The signature suggests that shear is more efficient at completely dispersing clouds, whereas feedback transforms the population, e.g. by fragmenting high mass clouds into lower mass pieces. Compared to the characteristic timescale for molecular hydrogen in M51, our short lifetimes suggest that gas can remain molecular while clouds disperse and reassemble. We propose that galaxy dynamics regulates the cycling of molecular material from diffuse to bound (and ultimately star-forming) objects, contributing to long observed molecular depletion times in normal disk galaxies. We also speculate that, in more extreme environments such as elliptical galaxies and concentrated galaxy centers, star formation can be suppressed when the shear timescale becomes so short that some clouds can not survive to collapse and form stars.