The Elliott-Yafet theory of spin relaxation in nonmagnetic metals predicts proportionality between spin and momentum relaxation times for scattering centers such as phonons. Here, we test this theory in Al nanowires over a very large thickness range (8.5-300 nm), finding that the Elliott-Yafet proportionality "constant" for phonon scattering in fact exhibits a large, unanticipated finite-size effect. Supported by analytical and numerical modeling, we explain this via strong phonon-induced spin relaxation at surfaces and interfaces, driven in particular by enhanced spin-orbit coupling.