Rutile germanium dioxide (r-GeO$_2$) is a recently predicted ultrawide-band-gap semiconductor with potential applications in high-power electronic devices, for which the carrier mobility is an important material parameter that controls the device efficiency. We apply first-principles calculations based on density functional and density functional perturbation theory to investigate carrier-phonon coupling in r-GeO$_2$ and predict its phonon-limited electron and hole mobilities as a function of temperature and crystallographic orientation. The calculated carrier mobilities at 300 K are $mu_{text{elec},perp vec{c}}$=244 cm$^2$ V$^{-1}$ s$^{-1}$, $mu_{text{elec},||vec{c}}$=377 cm$^2$ V$^{-1}$ s$^{-1}$, $mu_{text{hole},perp vec{c}}$=27 cm$^2$ V$^{-1}$ s$^{-1}$, and $mu_{text{hole},||vec{c}}$=29 cm$^2$ V$^{-1}$ s$^{-1}$. At room temperature, carrier scattering is dominated by the low-frequency polar-optical phonon modes. The predicted Baliga figure of merit of n-type r-GeO$_2$ surpasses several incumbent semiconductors such as Si, SiC, GaN, and $beta$-Ga$_2$O$_3$, demonstrating its superior performance in high-power electronic devices.