How to find out if a microprocessor is powerful enough

It depends on how confident you need to be. I work in the space industry and this is typically achieved via what we call "CPU, RAM, ROM budgets". A budget, be it cost power mass or anything else, is breaking down your process in manageable items which you can quantify and sum them all up to get the overall demand. You then take a safety factor that depends on the maturity of your project, decreasing with time to account for the growth in demand. Early on, it heavily relies on experience and then is refined over time as technologies are selected.

• ROM is relatively easy. You know how much a stack/library/driver roughly takes in ROM memory: either given by the author, or you can compile it without uploading it. That figure can change a lot every time you change your code though because of compiler optimisations.
• RAM is a lot trickier. Some tools in specialised integrated development environments give you runtime estimates, and I can see how this could be done but I'm not aware of any generic tool - say, provided by GCC (anyone knows otherwise?). Sadly it does sound like it's down to counting the biggest or most allocated elements of your code (accounting for variables lifetime).
• CPU is more complex in that depending on the architecture (CISC or RISC) the MIPS (Millions of Instructions Per Second, proportional to the CPU clock frequency) could or could not be representative. Because if you have the code at hand, you can break the most critical section down into instructions and calculate the required MIPS from the time requirement. Any non-disabled interrupt SHOULD be considered to be triggered at that point - Murphy's law and all that.

The above is extremely difficult to accurately determine when schedulers kick in, as soon as you have threads (unless threads are manually allocated to cores) and operating systems. It should be manageable for simple microcontroller codes, but is it worth it for your application?

This is only my participation: even though I design integrated systems I have not been responsible for those particular budgets (which are inputs for me), and I'm actually very interested to know experts' stories on that.

Addendum : With real-time systems, it is usually easier to assess the adequacy of the system to the task via the maximum sampling time which depends on latency/delays in the transmission of the information throughout the workflow, and the maximum time taken by each sample of task.

I am going to simplify your question to, "How to find out if a microprocessor is fast enough"?
You need to identify the process/procedure that requires the fastest execution time. If your processor can execute the instructions required in the given time, or less, then it is fast enough.
Lets look at an example: Your fastest requirement is to process a loss of power interrupt; this requires 10,000 instructions to be executed in 10 milliseconds. You will need a CPU with at least 1 MIP. To convert this to "MHz," you need to know the number of clock cycles per instruction (cci). Lets assume it is 10 cci, your CPU would need to run at 10 MHz, or faster.