Design begining phase..

Technically, you don't know until you're done. But you should be able to get a fairly good idea early on. Your performance is going to be based mainly on levels of logic, i.e. how much logic you do between registers. If you're not going super-fast(and I won't put a number to what that means, as it varies by family, speed grade, etc.), then you usually have quite a bit of logic to work with. What often happens is user's code something, it doesn't meet timing, and then they have to pipeline it(add registers along the critical path) in order to get it to meet timing. There's also dealing with placement, which has a big affect on timing.

Note that a LOT of large designs at large companies do not make timing all the time. These are designs from engineers who have tons of experience, but since the performance is usually driven more be a spec than by what the FPGA can do, they recode, redesign, and almost always get somethig to work.

And this isn't different than many other things. ASICs work the same way, just with a different threshold of super-fast. If you write some code for a processor, you usually don't know if it will meet your performance requirements(not Fmax, but system throughput) until testing it out. As you do more and get into this system, you'll quickly get more comfortable, but on a new design that you haven't done before, and if you haven't done a lot of FPGAs, you're just going to have to wade in and see what happens.