How to format a large diagram with many formulas that does not easily fit on an A4 page?
First, I do not consider your diagram is too big unless your layout has ridiculously big margins. That does not mean that you cannot improve its layout such that the type is bigger and thus easier to read.


  What to do to make the diagram easier to read?


Your biggest problem is that the individual formulas are all horizontal and very close together, which forces you to make them rather small. Thus, I suggest to replace most of your straight lines by curved ones and rotate your formulas appropriately. Also, use more vertical space (which you should have). Finally, you can make your texts narrower by using more line breaks:

A quick sketch to illustrate this:



Note that I increased the size of all formulas while maintaining the width.


  Should I replace big formulas with numbers or letters to label the arrows with numbers or letters and describe the corresponding formulas below (or above) the diagram (so called, "legend")? 


That sounds like a very bad idea to me. This way the reader would have to jump between diagram and legend all the time. The whole point of your diagram (as I understand it) is to have all these relation in one place. If you use a legend, you might as well skip the entire diagram and use text instead.