First-time iCloud backup of my iPhone took 26 hours
Honestly it depends on what you consider to be a LOT of videos.  Truthfully a 64 GB Phone filled on a standard Wifi home network should not take more than 10-15 hours at most.  Truth is the easiest way to see what is going on is go to www.icloud.com and check out your icloud space available.

The other thing to take into account is that you only get 5GB Free. You might have run out of space on iCloud and you didnt get the notifications.