Problem about interval timer

If it works with a lower frequency, it seems that the problem is rather in timing than in code.

Which version of the Nios II do you used (e/s/f) ? Because they have not the same performance, so if you don't use the fastest one, maybe try to use a faster version.

Else I would say to check the behaviour in simulation, like that you can check if the Nios II can process the interrupt in the time allowed and if it is a problem of of timing or not.