We have investigated the magnetoresistance (MR) in a series of Zn doped (p-type) GaAs nanowires implanted with different Mn concentrations. The nanowires with the lowest Mn concentration (~0.0001%) exhibit a low resistance of a few kΩ at 300K and a 4% positive MR at 1.6K, which can be well described by invoking a spin-split subband model. In contrast, nanowires with the highest Mn concentration (4%) display a large resistance of several MΩ at 300K and a large negative MR of 85% at 1.6K. The large negative MR is interpreted in terms of spin-dependent hopping in a complex magnetic nanowire landscape of magnetic polarons, separated by intermediate regions of Mn impurity spins. Sweeping the magnetic field back and forth for the 4% sample reveals a hysteresis that indicates the presence of a weak ferromagnetic phase. We propose co-doping with Zn to be a promising way to reach the goal of realizing ferromagnetic Ga_1-xMn_xAs nanowires for future nanospintronics.