What exactly is the bottleneck in your system/environment?

Is the power consumption the bottleneck?
As in, the system is maybe installed in a place where it cannot be 
connected to the power grid, thus has to run with a battery? Yes, in 
this case you would very much want to use a microncontroller that is 
optimized for low power consumption. The µC should sleep most of the 
time, and only wake up just often enough so that it can perform the 
tasks that it is supposed to do.

Is the computing time the bottleneck?
Computing time can be subsituted, to a degree, by using memory instead. 
Example: Instead of computing some trigonometric functions which are 
intense on the CPU, you could use a lookup table instead.

Is the available memory the bottleneck?
You can write code so that you really use each byte, and even each bit 
within a byte so as to get the most out of the available RAM. This will 
increase the size of your code though, since you will need more 
computing operations to e.g. mask out bits within a byte.

Without knowing the requirements that you need to implement, I don't 
think it is possible to give further help.