The Magellanic Clouds provide the only laboratory to study the effects of metallicity and galaxy mass on molecular gas and star formation at high (similar to 20 pc) resolution. We use the dust emission from HERITAGE Herschel data to map the molecular gas in the Magellanic Clouds, avoiding the known biases of CO emission as a tracer of H-2. Using our dust-based molecular gas estimates, we find molecular gas depletion times (tau(mol)(dep)) of similar to 0.4 Gyr in the Large Magellanic Cloud and similar to 0.6 in the Small Magellanic Cloud at 1 kpc scales. These depletion times fall within the range found for normal disk galaxies, but are shorter than the average value, which could be due to recent bursts in star formation. We find no evidence for a strong intrinsic dependence of the molecular gas depletion time on metallicity. We study the relationship between the gas and the star formation rate across a range of size scales from 20 pc to >= 1 kpc, including how the scatter in tau(mol)(dep) changes with the size scale, and discuss the physical mechanisms driving the relationships. We compare the metallicity-dependent star formation models of Ostriker et al. and Krumholz to our observations and find that they both predict the trend in the data, suggesting that the inclusion of a diffuse neutral medium is important at lower metallicity. ; NASA Herschel Science Center, European Space Agency (ESA), NSF grant