Can you run the software under a debugger or IDE?
Does the debugger have a "pause" button, or can you interrupt the program by typing Ctrl-C or some such keystroke?
If the program is getting slower and slower, it is doing at least one thing it doesn't need to be doing, and doing more and more of it.
Since it could be running in, say, 1/3 of the time it is currently running, that means 2/3 of the time it's doing things it doesn't need to do.
If you can take an X-Ray snapshot at a random point in time, chances are 2/3 you will see it doing the unnecessary thing(s).
Pause it while it's running, and examine what it's doing and why.
Especially examine every line of code on the call stack.
See if you can explain to yourself or someone else precisely why, in detail, that particular instant of time was being spent.
(You don't need to measure anything. You need to see if what it is doing can be gotten rid of.)
Repeat this a few times, like 5 or 10 times.
If what the program is doing at that point in time is not really necessary, and it is doing it on more than one time you stopped it, you have found something you can fix that will give you a big speedup, guaranteed.
The bigger the problem is, the quicker you will find it.
It's got nothing to do with requirements.
It's got nothing to do with measurements.
It's got everything to do with just "cleaning house", by this method.
Here's a fairly typical example.
Edit:
It's conventional wisdom to hear "measure measure" or "use a profiler".
What is not conventional is to hear how much speedup was achieved that way.
The few times I've heard the results of profiling, it was like 10% to 40%, or a factor of 1.1 to 1.4.
That's pretty anemic.
If a series of problems is found and fixed, there is a compounding effect, as shown in the example above.
P.S. Here's an example in C++ of a 3 order of magnitude speedup, containing all source code versions, copies of samples, and blow-by-blow description of how it is done. Some programmers have learned/discovered how to do this, but most have not. It couldn't be simpler.
To this day, I am still totally mystified that it is not common knowledge.
The only explanation I can see is that teachers don't work with programs large enough to require this kind of tuning.
What they do is teach gprof, for no other reason than that it's there, so they can teach it and move on.
What that does is infect their students with all the incredibly persistent myths of performance tuning, resulting in exactly the problems you describe.