How to decide the maximum frequency on FPGA?

Depends mainly on your design, and on the FPGA (type, speed grade) as 
well.

Define realistic but aggressive constraints (based on the FPGA datasheet 
and/or your requirements) and check the STA (static timing analysis) 
after synthesis:
- If the timing is met, go for a more aggressive setting.
- If the timing is not met do one (or more) of the following:
  - Relax the constraints.
  - Reduce the number of logic levels (between FFs) in your design.
  - Introduce pipelining registers.

Then restart the whole thing (it's iterative) until you are happy with 
the result.

P. K. wrote:
> - Relax the constraints.
hm, constraints are usually derived from specifications and functional 
demands, so one can hardly release them. The operation frequency of the 
FPGA is usually more or less directly linked to input data streams from 
chips, so one cannot go with lower freqs. On the other hand there is no 
demand for a maximum frequency.

Practically there is a range of a sensible operation frequency for every 
FPGA type. For e.g. a Spartan 6 device, one can reach 150MHz easily and 
up to 175 MHz with some work.

Jürgen Schuhmacher wrote:
> constraints are usually derived from specifications and functional
> demands, so one can hardly release them

I agree with you in a regular project environment, but the question 
seems to me somewhat more academic in a way to try the FPGA (the 
specification here is "as fast as possible").

Furthermore, only the interface timings might be fixed or have a clear 
maximum. That does not prevent you to have an internal master clock 
running as fast as possible with your given circuit (of course you have 
to bother about clock domain borders, but that's another story).