You may re-download deleted songs by going to [Play SingStar] > [Purchase History] from the game home screen and selecting the songs you want to download.
If you delete and re-download SingStar Ultimate to your PlayStation 4 you are given the option to choose which songs you would like to download with the full game:
You may download songs purchased previously for your PlayStation 3 versions of the game if they are also available for SingStar Ultimate.
When you download SingStar Ultimate to your new PlayStation 4 you are given the option to choose which songs you would like to download with the full game.
You may download your songs to a friend's PlayStation 4 when you temporarily activate their PlayStation 4 on your account and sign in on PlayStation Network (find out more about accessing your content from a friend's PlayStation 4 here).
You may re-download your songs when you re-download SingStar Ultimate. Follow the instructions for 'You have replaced your PlayStation console'.