We report on low-temperature magnetotransport and SQUID measurements on heavily doped Mn-implanted GaAs nanowires. SQUID data recorded at low magnetic fields exhibit clear signs of the onset of a spin-glass phase with a transition temperature of about 16 K. Magnetotransport experiments reveal a corresponding peak in resistance at 16 K and a remarkably large negative magnetoresistance, reaching 40 % at 1.6 K and 8 T. The negative magnetoresistance decreases at elevated temperatures and vanishes at about 100 K. We interpret our transport data in terms of spin-dependent hopping in a complex magnetic nanowire landscape of magnetic polarons forming a paramagnetic/spin-glass phase.