sp_delete_backuphistory not working
Delete Old Backup History
You might want to have a look at this stored procedure I created some time back. Instead of entering a date it gets the current date and goes 1080 days (default) back in time and starts deleting the backup history in steps of 1 (default) up until 180 days (default).
With a large msdb database you might have a lot of info that takes a long time to delete. Entering a simple date using the sp_delete_backuphistory procedure can cause issues, because it has to go a long way back in time to delete the information from the various tables.
My stored procedure is just a wrapper which automates the task of deleting old backup history using the built-in sp_delete_backuphistory (Microsoft | SQL Docs) procedure. The advantage of my procedure is that you don't have to manually enter dates to clean up the history in large msdb database, but can use days instead and can turn on transactional handling.

    use msdb
    go

    CREATE PROCEDURE [dbo].[spdeletehistory]
    /*
    -- ==================================================================
    -- Author......:    hot2use
    -- Date........:    04-Jan-2006
    -- Version.....:    1.3
    -- Server......:    [server name here]
    -- Database....:    msdb
    -- Name........:    spdeletehistory
    -- Owner.......:    dbo
    -- Table.......:    
    -- Type........:    Stored Procedure
    -- Description.:    Delete old backup history on a server
    -- History.....:    04-Jan-2006    1.0    First created
    --                  07-Dec-2005    1.1    Modified seperators
    --                  04-Jul-2006    1.2    Modified Text Output for return value
    --                                        Added Constants for defaults
    --                  25-Jan-2017    1.3    Slight modifications regarding comments
    --
    -- Editor......:    UltraEdit 11.10a (using Syntax Highlighting)
    --                    Tabstop Values = 4                    
    -- ==================================================================
    */
    
        /*input variables*/
        @iDaysBackToStart int = 0,
        @iDaysToKeep int = 0,
        @iDayStep int = 0,
        @iDebug int = 0
        
        /*output variables*/
        
    AS
    BEGIN
         /* Turn off double quotes for text strings */
        set quoted_identifier off
          /* Dont return the count for any statment */
        set nocount on
         /* debugging configuration */    
        declare @debug int
         /* debug settings
        1 = turn on debug information
        2 = turn off all possible outputs
        4 = turn on transaction handling
         e.g.: Adding an @iDebug paramter of 6 will... 
        ... turn on transaction handling (4) 
        ... turn off all possible output information (2)
         e.g.: Adding an @iDebug value of 1 will turn on all debugging information
        */ 
    
        set @debug = @iDebug
    
        /* day constants */
        declare @iDaysBackToStart_CONST int
        declare @iDaysToKeep_CONST int
        declare @iDayStep_CONST int
    
        /* constant settings
        set the defaults here instead of in the input variables
        it makes for easier changing, when comparing the default values in the code
        */
        set @iDaysBackToStart_CONST = 1080
        set @iDaysToKeep_CONST = 180
        set @iDayStep_CONST = 1
    
        if @iDaysBackToStart = 0
            BEGIN
                set @iDaysBackToStart = @iDaysBackToStart_CONST
            END
        
        if @iDaysToKeep = 0
            BEGIN
                set @iDaysToKeep = @iDaysToKeep_CONST
            END
        
        if @iDayStep = 0
            BEGIN
                set @iDayStep = @iDayStep_CONST
            END
        /*
        return values
        0 Successful execution. 
        1 Required parameter value not specified. 
        2 Invalid parameter value specified. 
        3 not defined
        4 not defined
        */
        declare @iRetVal int

        declare @dtDateToDelete datetime
        declare @dtCurrentDate datetime
        declare @dtStartDate datetime
        declare @dtStopDate datetime
        declare @vSQL nvarchar(2000)
        
        if @debug &amp; 1 = 1  print 'Checking variables...'
        if (@iDaysToKeep &lt; @iDaysToKeep_CONST) 
            BEGIN
                PRINT 'Invalid parameter value specified (1)'
                PRINT 'e.g. spdeletehistory @iDaysBackToStart = 1080, @iDaysToKeep = 180, @iDayStep = 1 '
                PRINT 'The default values are the above values'
                PRINT '@iDaysBackToStart must be &gt;= ' + convert(varchar(20), @iDaysBackToStart_CONST) + ''
                PRINT '@iDaysToKeep must be &gt;= ' + convert(varchar(20), @iDaysToKeep_CONST) + ''
                PRINT '@iDayStep must be &gt; ' + convert(varchar(20), @iDayStep_CONST - 1) + ''
                PRINT ''
                RETURN(2)
            END
        else if (@iDaysToKeep &lt; @iDaysToKeep_CONST) or (@iDaysBackToStart &lt; @iDaysBackToStart_CONST)
            BEGIN
                PRINT 'Invalid parameter value specified (2)'
                PRINT 'e.g. spdeletehistory @iDaysBackToStart = 1080, @iDaysToKeep = 180, @iDayStep = 1 '
                PRINT 'The default values are the above values'
                PRINT '@iDaysBackToStart must be &gt;= ' + convert(varchar(20), @iDaysBackToStart_CONST) + ''
                PRINT '@iDaysToKeep must be &gt;= ' + convert(varchar(20), @iDaysToKeep_CONST) + ''
                PRINT '@iDayStep must be &gt; ' + convert(varchar(20), @iDayStep_CONST - 1) + ''
                PRINT ''
                RETURN(2)
            END
        else
            BEGIN
                if @debug &amp; 1 = 1  print 'Checking if just defaults have been used...'
                if (@iDaysToKeep = @iDaysToKeep_CONST) and (@iDayStep = @iDayStep_CONST) and (@iDaysBackToStart = @iDaysBackToStart_CONST)
                    BEGIN
                        if @debug &amp; 2 &lt;&gt; 2 
                            BEGIN
                                PRINT ''
                                PRINT 'Running with default parameters'
                                PRINT ''
                                PRINT '@iDaysBackToStart ='  + convert(varchar(20), @iDaysBackToStart_CONST) + ''
                                PRINT '@iDaysToKeep = ' + convert(varchar(20), @iDaysToKeep_CONST) + ''
                                PRINT '@iDayStep = ' + convert(varchar(20), @iDayStep_CONST) + ''
                                PRINT ''
                            END
                    END
                -- if @debug &amp; 1 = 1 
                if @debug &amp; 1 = 1  print 'Settings date variables...'
                select @dtCurrentDate = getdate()
                if @debug &amp; 1 = 1  print '@dtCurrentDate..: ' + convert(varchar(60), @dtCurrentDate, 20)
                select @dtStartDate = @dtCurrentDate - @iDaysBackToStart
                if @debug &amp; 1 = 1  print '@dtStartDate....: ' + convert(varchar(60), @dtStartDate, 20)
                select @dtStopDate = @dtCurrentDate - @iDaysToKeep
                if @debug &amp; 1 = 1  print '@dtStopDate.....: ' + convert(varchar(60), @dtStopDate, 20)
                select @dtDateToDelete = @dtStartDate
                if @debug &amp; 1 = 1  print '@dtDateToDelete.: ' + convert(varchar(60), @dtDateToDelete, 20)
                
                if @debug &amp; 1 = 1  print 'Starting to loop...'
                while @dtDateToDelete &lt; @dtStopDate begin
                    
                    set @vSQL = 'msdb.dbo.sp_delete_backuphistory ''' + convert(varchar(60), @dtDateToDelete, 20) + ''''
                    if @debug &amp; 1 = 1  print '@vSQL.........: ' + @vSQL
                    if @debug &amp; 4 = 4
                        BEGIN
                            begin tran john
                        END
                    exec @iRetVal = sp_executesql @vSQL
                    if @iRetVal &lt;&gt; 0 
                        BEGIN
                            /* Turn on double quotes for text strings */
                            set quoted_identifier on
                            
                             /* Return the count for any statment */
                            set nocount off    
                            
                            /* If transactions have been turned on then rollback if failed */
                            if @debug &amp; 4 = 4
                                BEGIN
                                    rollback tran john                        
                                END
    
                            /* If general output has not been turned off print output*/ 
                            if @debug &amp; 2 &lt;&gt; 2 
                                BEGIN
                                    PRINT 'Return Value: ' + convert(varchar(100), @iRetVal) + ' at current time: ' + convert(varchar(20),getdate())
                                end
                            RETURN(@iRetVal)
                        END
                        
                    /* If transactions have been turned on then commit on success */
                    if @debug &amp; 4 = 4
                        BEGIN
                            commit tran john
                        END
                        
                    /* If general output has not been turned off print output*/ 
                    if @debug &amp; 2 &lt;&gt; 2 
                        BEGIN
                            PRINT 'Return Value: ' + convert(varchar(100), @iRetVal) + ' at current time: ' + convert(varchar(20),getdate())
                        end
                    /* Get next date to delte history data */                    
                    select @dtDateToDelete = @dtDateToDelete + @iDayStep
                end
            END
        /* Turn on double quotes for text strings */
        set quoted_identifier on
         /* Return the count for any statment */
        set nocount off    
        /* If general output has not been turned off print output*/ 
        if @debug &amp; 2 &lt;&gt; 2 
            BEGIN
                print 'Finished.'
            END
        RETURN(0)
    END
    GO    

Once you have the procedure in your msdb database, then run the query via:
msdb.dbo.spdeletehistory

The stored procedure will then run with the default values:
@iDaysBackToStart = 1080
@iDaysToKeep = 180
@iDayStep = 1

You can change these values to meet your requirements. For example:
spdeletehistory @iDaysBackToStart = 2000, @iDaysToKeep = 180, @iDayStep = 2

If you want lower values than the defaults, then you will have to modify the @i..._CONST values in the stored procedure, as the defaults are the lowest values possible.
If you want to see what happens, then set the @iDebug parameter (bitwise):
/* debug settings
1 = turn on debug information
2 = turn off all possible outputs
4 = turn on transaction handling
e.g.: Adding an @iDebug paramter of 6 will... 
... turn on transaction handling (4) 
... turn off all possible output information (2)
e.g.: Adding an @iDebug value of 1 will turn on all debugging information
*/

E.g. turning on @iDebug = 4 will delete the history in transactions which can reduce the overall impact on the msdb database.
Example Run
Running the following command:
msdb.dbo.spdeletehistory @iDaysBackToStart = 1080, @iDaysToKeep = 180, @iDayStep = 1, @iDebug = 7 

Produces the following output:

Checking variables...
Checking if just defaults have been used...
Settings date variables...
@dtCurrentDate..: 2020-07-03 13:25:20
@dtStartDate....: 2017-07-19 13:25:20
@dtStopDate.....: 2020-01-05 13:25:20
@dtDateToDelete.: 2017-07-19 13:25:20
Starting to loop...
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-19 13:25:20'
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-20 13:25:20'
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-21 13:25:20'
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-22 13:25:20'
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-23 13:25:20'
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2017-07-24 13:25:20'
....
@vSQL.........: msdb.dbo.sp_delete_backuphistory '2020-01-04 13:25:20'


This should clear up old backup information in the msdb database.
However, it will not shrink the msdb database.  That's a different issue, which can be achieved with ...
DBCC SHRINKFILE
The DBCC SHRINKFILE (Microsoft | SQL Docs) command can be used to reclaim space that was once used in a database. It is not recommended for general use, as a database will normally reclaim the released space again in most cases, but seeing as you have a rather large msdb database....
USE [msdb]
GO
DBCC SHRINKFILE (N'MSDBData' , 0, TRUNCATEONLY) -- release unused space
GO

USE [msdb]
GO
DBCC SHRINKFILE (N'MSDBData' , 96) -- shrink mdf data file to 96 MB size
GO

Please be aware that if the msdb database is under pressure that you might not be able to actually shrink the database in one go.
You might not even be able to shrink the database down to 98 MB. If you right click the msdb database and then select: TASK... | Shrink ... | Files ... you will be presented with a dialog that will tell you the minimum size, that the database file(s) can be shrunk to. Take that value and add it to the second command:
USE [msdb]
GO
DBCC SHRINKFILE (N'MSDBData' , 1024) -- shrink mdf data file to 1 GB size
GO

Good luck.