Why do real-time clock chips use BCD
Do all RTCs use BCD encoding?

RTCs from Philips/NXP (both standalone and integrated into ARM7 or Cortex-M3 chips) do not use BCD encoding.

What's wrong with a BCD RTC?

When compared to flat counter the only operations which are more difficult with a split BCD clock are time difference calculations (adding seconds or calculating elapsed time). Time comparisons like: "is current time greater than the alarm time set by the user" are just as easy.

What's nice about BCD (and generally split-field) RTCs?

Splitting the fields is really nice when you care for the calendar date. Human calendars have funny things like months of different lengths and on top of that leap years. Try to do that in a single counter (you can get a bonus point for using almost no power). Oh and try supporting week days (quite useful in all kinds of devices meant for humans: from alarm clocks to heater controllers) with this.

The BCD approach has one additional feature: you get "every second" or "every ten seconds" interrupts for free, without having to do any calculations on times or dates.

For the record leap year calculation is a little off in the NXP RTCs since it only cares for the divisible by 4 rule and does not check the division by 100 and 400. If it kept the year counter in BCD this would be trivial and most probably done right.

Summary


If you want a monotonic clock then use one. You can buy a PIC or AVR with the "RTC counter" (which is just an asynchronous counter with an autonomous 32kHz oscillator). Just keep in mind that simply displaying the date will be difficult. :)
When you need to display the time and date and set alarms based on user input of times and dates then use an RTC. And remember that when the user changes the current time and date your RTC based interrupts may be inaccurate.