HC-05, can't pair it with phone

Hey everyone, Recenty I bought an HC-05 bluetooth module, some motors, propelers... Thought it would be cool to make a bluetooth controlled boat. Sadly just as I started working on the project I faced first serious problem- I can't pair the HC-05 module with my phone (The phone doesn't catch the signal).

I've been searching the internet for solution, found lots of them, but couldn't go far, since most of them show the example with arduino UNO(mine's MEGA2560). Also been trying to switch the AT modes, because I thought that it is set on the wrong mode. Couldn't figure out that aswell. I can make the light on the bluetooth module slown down to blink per 2 seconds(which indicates that the module is in the AT mode), but get no response when trying to communicate with it through serial monitor(9600baud and "Both NL &CR").

Also I've noticed that I can't upload the code while the HC-05 is attached to the circuit, of course I can detach it for a while.

I starting to think that I might have burned down the module somehow. Are there any simple methods to know whether the module is working properly? I have an UT33C multimeter, ?maybe I can do something with it

I have never worked with bluetooth before. Any help would be appreciated.

I'm not adding the code, because I tried lots of them and none of them worked.

Wires:
(Arduino)-(HC-05module)
(GND)-(GND)
(5v)-(VCC)
(RX0)-(RXD)
(TX0)-(TXD)

You might find the following background notes useful.

http://homepages.ihug.com.au/~npyner/Arduino/GUIDE_2BT.pdf
http://homepages.ihug.com.au/~npyner/Arduino/BT_2_WAY.ino

They deal specifically for Mega, but anything you read about Uno could have been applied.

As things are, it is not clear that you understand what pairing is. It is indeed a prerequisite for catching the signal, but not part of the process. This all assumes that you are aware that HC-0x is incompatible with iPhone and you are using a proper Android.

Your wiring is wrong in your words but apparently OK in the pictures.

Forget about AT mode for the moment. You don't need it and may never need it, but you do need to learn to walk before you learn to run.

The devices are in the right mode by default, you probably haven't set anything in the wrong mode, and, if you did, it can be fixed - but only after you have proven that there is a problem.

You are right to use hardware serial but you have three more ports on a Mega and are not obliged to disconnect while uploading if you use one of the others.

You probably haven't burned down anything. If you can see a flashing LED, it is probably OK.