The main reason behind this is Megatron's own ability to perceive the attributes of Starscream. Perhaps he sees a little of himself in Starscream, if not the physical part, at least the "cunning part" definitely. This prompts him to reconsider his decision of killing Starscream; Starscream may inadvertently come up with a useful idea to demolish the Autobots, which Megatron then can use at his own discretion.
Having said that, Megatron is in a dilemma. He is constantly toying with the idea of either having Starscream terminated or banished. He seems just not able to make up his mind, due to his past association with Starscream. Also, due to the same reason he may think, that Starscream will never be able to outwit him.