Linear magnetoresistance (LMR) is of particular interest for memory, electronics, and sensing applications, especially when it does not saturate over a wide range of magnetic fields. Structural disorder, however, also tends to limit the mobility and hence the overall LMR amplitude. An alternative route to achieve large LMR is via nonstructural inhomogeneities which do not affect the zero field mobility, like magnetic domains. Here, we report a colossal positive linear magnetoresistance in LaTiO3/SrTiO3 heterostructures, with amplitude up to 6500% at 9T at low temperature. The colossal amplitude of the LMR, one of the largest in oxide heterostructure, stems from the unusual combination of a very high heterostructure mobility, up to 40 000 cm2V-1s-1, and a very large coverage of low-mobility regions. Low-temperature Lorentz transmission electron microscopy measurements further reveals a striped magnetic structure at the sub-μm scale in the LaTiO3 layer, compatible with in-plane spiral magnetism, with very high surface coverage. We propose that the low-mobility regions and striped magnetic regions are correlated, we model the increase in scattering induced by the magnetic texture, and we show that the non saturating LMR fits the Parish-Littlewood scenario. Our results provide a novel route for the engineering of large-LMR systems, using magnetic texture.