Board size vs component size
Obviously if you have no traces between components, parts can be spaced extremely tight.  The top figure a) assumes a clearance of 0.15 mm, or 6 mils, which is the default for Eagle.  The middle figure b) includes traces and vias again with spacing and trace size assumed to be 6 mil..

It's possible to make a reasonably good estimate for a board, but it will take a fair amount of work if traces have to be accounted for.   If assumptions can be made about the number of traces (because it's a multi-layer board), then things become much easier.

For one component, the space required (assuming no traces or vias) is:

$$A = (l+c)\times(w+c)$$

where A is the area, l = length, w = width, and c is clearance.

For parts with at least one trace on one or both sides, it is:

$$A = (l + c + t2c + x2c)\times(w + c + y2c + z2c)$$

where A is the area, l = length, w = width, and c is clearance, t and x are the number of traces or vias across one or both ends, and y and z are the number of traces or vias along one or both of the sides.  A via feeding into a resistor counts the same as a trace.

This could be done either in mm or mils, as long as the same system is used for everything.  I'm assuming the clearance between traces and the trace width are the same.

If this is going to be a multi-layer board, then one can assume almost all of the traces will be on the bottom or middle layers and the top will be just vias, like figure c).  In that case, as a first approximation just assume a via for each pin. 

For large parts, like a µC which has a lot of pins spaced closely together, allow for two rows of vias.  I'm not allowing for the fact that parts like that can have several vias underneath them and/or there are no pads visible (like a QFN package).

So now you have a lot less work -- just the area of the components, plus the room needed for the vias.  The formulas reduce to these four simplified ones (no estimating the number of or likely placement of traces):

For rectangular parts with pads at each end, like resistors or caps:

$$A = (l+5c)\times(w+c)$$

For rectangular parts, with pins along the side (like SOIC packages etc.):

$$A = (l+c)\times(w+5c)$$

For rectangular parts, with pins along the sides and at the ends:

$$A = (l+5c)\times(w+5c)$$

For large square components, with pins all around:

$$A = (l+9c)^{2}$$

These assume there are hardly any traces on the component side(s); i.e. at least a four layer board with two signal layers.   So these areas are fixed for each type of component; they don't vary by the number of traces.

If this was fed into a spreadsheet, with formulas set up for each component size (like a 0805 resistor or cap), it won't be too bad. You only need one value for each type of component.  Count the number of each different size and add them up (e.g. both resistors and capacitors may come in 0603 packages -- you don't need separate entries for each).

Remember to allow space for the pads at either end of a component -- for example the resistor length only includes the body.  A 0603 (1608 metric) resistor is 1.6 mm long by 0.8 mm wide, but including the pads, it is 2.8 mm long. These footprints will be defined in the component library for your PCB layout program. 

So for a 0603 resistor, the area needed (including the pads and vias at each end) would be:

$$A = (l+5c)\times(w+c)$$

$$A = (2.1 + 5\times 0.15)\times(0.9 + .15) = 2.85\times 1.05 = 2.99\space  mm^{2}$$

The area of just the body of the resistor (1.6 mm x 0.8 mm) is a little less than half that -- 1.28 mm².  The footprint (including the pads) is 2.1 mm x 0.8 mm or 1.68 mm².  So using either of those plus a fudge factor of even 20% is not going to work.  The minimum clearances needed for just one via or trace constituent almost half of the area.

With smaller parts, the clearances dominate even more.  For a 0201 resistor (0603 metric, i.e. 0.6 mm by 0.3 mm), the required area is:

$$A = (0.75 + 5\times 0.15)\times(0.3 + .15) = 1.5\times 0.45 = 0.68\space  mm^{2}$$

compared to a component size of 0.18 mm² and a footprint of 0.22 mm².  In this case, the footprint (including recommended pad area) only accounts for 1/3 of the needed area.

With a spreadsheet you could vary the numbers around (making some worst and best case estimates) and at least get a rough idea.  Perhaps change all of the resistors from 0603's to 0201's and see what difference that makes  -- or go from a 100-pin µC to a 64-pin one -- or change the clearance size.