If you are making a project proposal then take your best guess based upon experience and bias the guess high. If you have not experience to draw from, well then you have a problem. If this isn't good enough and you require an exact answer then you will probably have to go ahead and implement the logic in the tools and see what size devices it requires. Unfortunately, I know of no magic to tell you how many gates you are going to require.
Regarding CPLD / FPGA, in generall FPGAs are a lot larger than CPLDs and can have a lot higher density per dollar. CPLDs, however are usually flash based so that they don't require a bootup time / sequence and a configuration method. Lastly, CPLDs tend to be more of an AND/OR array strucutre while FPGAs utilize a ram lookup with a mux architecture. Consequently one may take more or less resources based upon the design.