This isn't simple. There are several ways of explaining what the adverb 'really' is doing in sentences like this. It's an adverb, and as anyone with a basic understanding of the parts of speech knows, that means it modifies adjectives (or adjectivals generally) and verbs. Actually, there are circumstances in which adverbs can modify noun phrases as well, but we'll leave that aside for now.
What is 'really' modifying in these examples? Let's look at other examples that work similarly, and examples without negation.
"I'm really hungry."
Here it's essentially synonymous with very, indicating degree.
"I'm not really angry."
Here's our first ambiguous example. If emphasised in a certain way, it could be an admission that you are not, in actual fact, angry at all. That shows the origin of really as the adverb form of the adjective real, real-ly. You might say that if you'd been pretending to be angry, or if someone had been told that you were angry when you weren't. Emphasised in another way, it takes the same meaning as the previous example, modifying angry by degree. In the second case, it is an adverb modifying an adjective again. In the first case, it is an adverb modifying the verb to be.
"I'm really not angry."
This might be said by someone trying to convince another person that they aren't angry. They are trying to convince them of the reality of their non-anger. It can thus be seen as addressing the reality of the negation not. You could also see it as an intensifier of not as well.
"I'm not really sure."
I have an idea, but I lack certainty. Adverb modifying adjective again. This suggests that there's the start of certainty, but it's not fully formed. "I'm not sure" would convey lack of certainty; the really might be acting to suggest you are somewhat sure, but not entirely, or be an essentially meaningless extra word thrown in to no good effect.
"I'm really not sure."
Here the emphasis is again on the not. It intensified the lack of certainty.
"I'm not sure, really."
Here really modifies the entire clause, indicating that it is 'real'. It asserts that the statement is true. If stressed, it is intensifying the whole statement, asserting its reality strongly. If not stressed, it might just be a pointless extra word. We do that a lot in English.
"You're not really going to give me $5, are you?"
Expressing either doubt or a sincere conclusion that a person is not going to do something they said they were going to do.
"I'm really going to give you $5."
Asserting that you really are going to do that.
"You're really not going to like this."
Intensifying the not; the degree to which the person is going to not like it is expected to be high.
"You're not really going to like this."
Depending on stress, it might be changing an expectation; you may have said they will like it, but are now admitting they won't. Without that stress, it instead makes it milder. It could be something that one might expect that they would like, perhaps. However, that sense of making it milder may be used ironically, suggesting that in fact they are definitely not going to like it.
"You're not going to really like this."
Would only be used with stress on the really, where it acts to intensify like. As it is covered by the negation, this means that you may like it, but that like is not going to be particularly intense.
So far, we can see a range of ways it works with adjectives and verbs. We can see that your examples may fits these patterns, but 'a leader' isn't an adjective or a verb. It's a noun phrase. There are documented cases of adverbs modifying noun phrases, even where they consist of a single noun. So, we might simply apply these patterns on that basis. Or we might say that in your second example, "not a leader" is acting as an adjectival phrase. We might even consider "a leader" in the same way, because although it is a noun it is in a position that an adjective could occupy. You might think of "not really" as a set phrase that has developed from its more regular usages with verb and adjectives.
There are various ways it could be explained, and I rather suspect linguists vary as to how they would do it. As an educated native speaker, I don't pretend to have authoritative answers. Whatever the explanation, the effect is that your first example could mean:
- David has been presented as a leader, or has claimed to be a leader, and is not.
- David has some characteristics you would expect from a leader, but not enough or in great enough degree.
- As a form of ironic understatement to suggest that there is no way that David could be considered a leader.
In all those cases, it might be rephrased as "Davis is not a real leader."
The second example you give is stating emphatically that David is not a leader.