If you're using NIOS 2 there is a profiler component (performance counter unit) you can add to your system. I've never used it myself so I don't know how it works.
I guess you could make one of those yourself, a write to a sopc component would start a counter and then with another write stop it and read out the value. A start and stop of the timer would give you an estimate of the avalon overhead.
You could also use a timer in your NIOS 2 core to see how long time the program takes to execute and then estimate the number of cycles.
I hope this helps