In analogy to electron-phonon coupling (EPC), electron-magnon coupling (EMC) is expected to shape electronic structure, transport, and possibly unconventional superconductivity in magnetic materials. However, unlike EPC, which is now routinely treated within first-principles frameworks, a quantitative description of EMC, especially for transport, remains elusive because of the lack of theoretical formalism. Consequently, even for elemental iron, EPC-only calculations miss both the magnitude and the T² component of resistivity. This discrepancy has long been attributed to EMC, although direct computational evidence has been lacking and the underlying transport mechanism remains unresolved. Here we develop a unified first-principles formalism for EMC in collinear magnetic systems within many-body perturbation theory, complemented by machine-learning spinful Hamiltonians that supply quantities not directly accessible from conventional first-principles methods. Our framework enables ab initio transport calculations including EMC effects for the first time. Applied to ferromagnetic α-Fe, our approach yields electron spectral functions consistent with previous studies. More importantly, we recover the full T² component of resistivity with a coefficient in quantitative agreement with measurement and reveal that the T² component cannot be attributed solely to EMC, as has long been assumed, but is dominated by the strong EPC-EMC interplay. Extending to antiferromagnetic K-doped BaMn₂As₂, our method captures the ARPES-observed magnon-induced kink and a large EMC strength of ∼ 3 comparable to experimental measurements, demonstrating the generality of the framework. Our work closes a longstanding gap in the quantitative understanding of transport in magnetic systems and provides a predictive foundation for examining magnon-mediated phenomena.