Severe plastic deformation (SPD) techniques have been used extensively over the past 40 years for producing strong metals and alloys. High-pressure torsion (HPT) is one of the most promising SPD techniques for achieving high strength through nanoscale grain refinement and phase transformation. In this research, a mixture of pure zinc (Zn) and magnesium (Mg) powders, Zn-3Mg (wt%), was HPT-processed under a pressure of 6 GPa for 1, 5, 10, 20, and 30 turns at room temperature to achieve a high strength biodegradable material. In order to understand the effects of pre-consolidation on the resulting microstructure and hardness, HPT processing was performed on loose powders placed in the die and also on a pre-compacted powder mixture and characterized by X-ray diffraction, scanning electron microscopy, atom probe tomography, and Vickers microhardness. In both cases, the microstructures contained nanoscale grains, and stable and metastable strain-induced intermetallics, but an unusual softening appeared at large shear strains. Grain size, grain morphology, and the formation of different intermetallics were analyzed to explain the unusual hardness distribution, and it was found that an inverse Hall-Petch relationship between hardness and grain size exists. It is suggested that thermally-activated phenomena such as grain boundary sliding contribute to the strain-induced softening of this nano-structured biomaterial due to its low melting point. The current results are compared with those for HPT-processed cast alloys and hybrids of the same composition.