Microorganism motility often takes place within complex, viscoelastic fluid environments, e.g., sperm in cervicovaginal mucus and bacteria in biofilms. In such complex fluids, strains and stresses generated by the microorganism are stored and relax across a spectrum of length and time scales and the complex fluid can be driven out of its linear response regime. Phenomena not possible in viscous media thereby arise from feedback between the swimmer and the complex fluid, making swimming efficiency co-dependent on the propulsion mechanism and fluid properties. Here we parameterize a flagellar motor and filament properties together with elastic relaxation and nonlinear shear-thinning properties of the fluid in a computational immersed boundary model. We then explore swimming efficiency, defined as a particular flow rate divided by the torque required to spin the motor, over this parameter space. Our findings indicate that motor efficiency (measured by the volumetric flow rate) can be boosted or degraded by relatively moderate or strong shear-thinning of the viscoelastic environment.