How to divide tasks to be done by Nios II processor & Logic elements?

500 lines is a meaningless figure - it depends what the lines do.

In particular what they require from any system libraries.

My multi-channel hdlc engine is just over 1000 lines (500 contain a ';') and compiles to about 2k of object code (with no support libraries).

The current version uses custom instructions to speed up the crc and bitstuffing and needs about 170 clocks per byte.

A pure hdlc version would be must faster, but all the complex decision making is much easier in software.