I think it began a lot earlier than 6 million years ago. Elephants show grief at death. Monkeys and apes are distressed when an infant dies, etc.
One day I was very upset and visiting a friend. I was lying on the bed crying and his Sheltie jumped up on the bed, snuggled against me and whined in sympathy.
Some exotic species of birds reportedly bond with their owners as well and mourn after their passing.