Constraining SDRAM

Setting multicycle 2 would give you additional 16ns, as you said, but that's not what you need.

Infact this assumes the sampling device waits one more cycle before latching the data into the register. So you can use multicycles where the system really perform multicycle accesses, for example if it explicitly requires delays or waitstates.

Otherwise TQ would tell you the design meets timing but actually it will NOT work.

In general, setup violations are frequency dependent, while hold violations are not; so you can get rid of negative setup slack if you reduce frequency. Going back to your original post, you can try to reduce system frequency from 62.5 to 50MHz: if the random problem still remains the same, it's probably not a setup timing issue.

Last remark: did you try a sdram clock shift reduced to about -1ns as I suggested?

I checked your memory datasheet and it matches mine. Moreover I use a EP3C40, so I guess what is good for me should probably be good for you. With the -0.75 phase shift I could always operate my design without problems from 50 to 100MHz.