How do I come up with a list of requirements for a microcontroller for my project? How can I then find microcontrollers that fit?
(This is a generic guide. I suspect you could also benefit from code optimisation, but that's outside the scope of this website.)

Step 1: Rough sizing, budget, vendor

Pick one of:


Computer (Raspberry Pi, Beagleboard, PC104 board, Intel Edison, etc). Boots a general-purpose operating system and has lots of processing power. More expensive and power-hungry. $10-$100.
Large MCU. ARM Cortex-A / PIC32 / dsPIC / AVR32 / TI C series DSP etc. Decent computing power, OS optional. ~$5.
Small MCU. Cortex-M / PIC16. Not really enough space for a true OS, maybe just a lightweight task scheduler. ~$2.
Tiny MCU. Only really for applications where you care about every last microamp of power consumption. ~$1 or less.


You should also consider at this stage which vendors and toolchains you like and dislike. Have a look at the cost of things like in-circuit debugging devices and IDEs.

Step 2: Minimum Peripherals

Do you need things like USB? PCI? HDMI? SATA? Unusually fast ADCs or DACs? Almost all of the "small" or "tiny" category do not have these, although USB is fairly widely available.

Step 3: Prototype

Pick something which meets the above criteria, at random if necessary, make a start, find out how feasible it is and how much space / processing power you need. You've already done some of this. Writing in C should make much of the logic portable. 

Once you have the prototype you can say to yourself, "I need one like this, but with more X" and let that guide your decisions.

Step 4: Shrink

It's generally easier to start with the largest (most Flash and RAM) member of a CPU family, write v1 of your application, and then choose a smaller, cheaper one to fit. You can also spend time on the art of fitting software into fewer resources. What's worthwhile depends on how many units you're going to make.