Either mail or send is fine - implicit in the use of 'send' is that you will use some third party intervention for the gift to reach the recipient - and this would be understood to be the mail system, unless you specify some other means. Eg, I am sending a gift to my sister in Australia with my friend, who is going there next month. Be aware that British English speakers are very likely to use 'post' instead of mail. We 'post' letters rather than mail them. And our letters/parcels are delivered by a 'postman', rather than a 'mailman'.

You can use both send/mail. Mail specifically refers to the use of a mail system. For (2) - you would say "I haven't received the gift yet" "the gift hasn't reached me yet" "the gift hasn't been delivered"