Put your scope on the reset line. Then open the serial monitor. Watch how long reset is held low.
Here is the pic I took. The reset of the Mega2560 is on channel 1. When I open the serial monitor, it goes down from 5V to less than 1V and goes back to 5V within 3 ms.
That's pretty strange. That pic looks OK.
You could try flipping the BOOTRST fuse so that the bootloader is not invoked. That rules in or out the bootloader somehow being the problem.
(Make the HIGH fuse 0xD9).
When I try that, there is no delay.
So, the problem must be with the bootloader, right ?
Well, it depends how you define "problem".
That same bootloader on my official Mega 2560 board does not have a delay. So it is more likely to be a combination of the bootloader waiting for something, and the circuit making it thing that waiting 9 seconds is worthwhile.
There is absolutely no activity on either Rx/Tx pins ...
Yes, but are they high or low? If they are low try putting pull-up resistors on them, or just try that anyway.
There are both high.
The question is why my circuit, although working as expected, is making the bootloader not working as it should ?
Could the RX pin be floating/picking up noise and the bootloader is trying to read this as the programming info it expects but after some seconds it either gives up of the cause of the noise abates and it starts the main program.
I have inspected both signals with my oscilloscope and I didn't see anything there. If it's a problem of noise on the Rx with my setup, I think some people would have experienced the same problem with the Arduino Mega2560.
Maybe the bootloader is really waiting for something. But what and why ?
gabidanpremier:
I have inspected both signals with my oscilloscope and I didn't see anything there. If it's a problem of noise on the Rx with my setup, I think some people would have experienced the same problem with the Arduino Mega2560.Maybe the bootloader is really waiting for something. But what and why ?
No signal seen at all, no steady low, no steady high? Maybe you forgot to turn on the scope? 
Lefty
Oh, you're right. Here is the corrected sentence:
I have inspected both signals with my oscilloscope and I didn't see anything problem there.
The signals were steady 5V.
Did you put the pull-up resistors on them?
We are running out of other options, that's why I suggest it.
Hey I have the same exact issue with my mega2560. But mine is a genuine arduino I bought. It works perfectly but if I open serial monitor it take about 10 secs to start running again. BUT if I open the serial monitor I can press the reset on the mega and it will start right away?
PavelK, this exactly the same problem for me. I'm glad to know it's not a problem with my board 
!
On my board, if I reset the board while serial monitor is open, it starts immediately. You can try.
See reply #30.
I don't understand why I need the phillip resistors one either Tx or Rx pins. I will try that. Also I'm kinda new to arduinos. How do I edit the fuses?
Btw my brother had a mega2560 and has same problem. It's not really a big problem just wondering why it does that.
How do I edit the fuses?
Cautiously. If you change the wrong things you may brick the processor. Make sure you understand what you are doing. Preferably key in your existing fuse values into a calculator, and then just change one bit.
http://www.engbedded.com/fusecalc
If you have an external programmer you can change them with avrdude (like an USBtinyISP programmer for example).
PavelK, if you've never changed the fuses settings on your Mega2560, I don't think there is a reason why you would do it now.
If you just want to solve the 10 sec issue, you wont solve anything by playing with the fuses settings.
I agree. I don't know of any "wait 10 seconds before doing anything" fuse.