Controller for a Brushless DC motor (with ESC)
If the nonlinear relationship holds for a wide variety of conditions, you could create a mapping function that removes the nonlinearity. The only issue would be if the function is non-monotonic (ie has a dip).
Of course, you could always just apply the PID and experiment with parameter values. Unless the system is VERY badly behaved, you will probably find a result you like.

TL;DR Stop worrying and just try it