Topological materials often exhibit remarkably linear, non-saturating magnetoresistance (LMR), which is both of scientific and technological importance. However, the role of topologically non-trivial states in the emergence of such a behaviour has been difficult to establish in experiments. Here, we show how strong interaction between the topological surface states (TSS) with a positive g-factor and the bulk carriers can lead to a smearing of the Landau levels giving rise to an LMR behavior in a semi-metallic Heusler compound. The role of TSS is established by controllably reducing the surface-bulk coupling by a combination of substitution alloying and the application of high magnetic field, when the LMR behavior transmutes into a quantum Hall phase arising from the TSS. Our work establishes that small changes in the coupling strength between the surface and the bulk carriers can have a profound impact on the magnetotransport behavior in topological materials. In the process, we lay out a strategy to both reveal and manipulate the exotic properties of TSS in compounds with a semi-metallic bulk band structure, as is the case in multi-functional Heusler compounds.