Lead-free halide double perovskites have attracted considerable attention as complements to lead-based halide perovskites in a range of optoelectronic applications. Experiments on Cs2AgBiBr6 indicate carrier mobilities in the range of 0.3-11 cm2/(V s) at room temperature, considerably lower than in lead-based perovskites. The origin of low mobilities is currently unclear, calling for an atomic-scale investigation. We report state-of-the-art ab initio calculations of the phonon-limited mobility of charge carriers in lead-free halide double perovskites Cs2AgBiX6 (X = Br, Cl). For Cs2AgBiBr6, we obtain room-temperature electron and hole mobilities of 17 and 14 cm2/(V s), respectively, in line with experiments. We demonstrate that the cause for the lower mobility of this compound, compared to CH3NH3PbI3, resides in the heavier carrier effective masses. A mode-resolved analysis of scattering rates reveals the predominance of Fröhlich electron-phonon scattering, similar to lead-based perovskites. Our results indicate that, to increase the mobility of lead-free perovskites, it is necessary to reduce the effective masses, for example by cation engineering.