Further exchange on https://debbugs.gnu.org/35289 suggests this is a libc6 problem, not a coreutils/date one.

Assaf Gordon (upstream) provided a test that can be run (attached here are inv-year.c). If it fails on the mktime() call, then it is not 'date', but libc6.

I also found that setting TZ=UTC seems to bypass the problem; in my primary test machine, TZ was unset (but I was still getting a failure). Setting TZ to UTC, or an invalid value, works. Setting TZ=America/Chicago fails (perhaps related to DST?):

cerdea@piatam:~/Downloads$ env TZ=UTC date --debug +%-Y -d '- 2010 years'
date: parsed relative part: -2010 year(s)
date: input timezone: TZ="UTC" environment value
date: using current time as starting value: '17:28:13'
date: using current date as starting value: '(Y-M-D) 2019-04-16'
date: starting date/time: '(Y-M-D) 2019-04-16 17:28:13'
date: warning: when adding relative months/years, it is recommended to specify the 15th of the months
date: after date adjustment (-2010 years, +0 months, +0 days),
date:     new date/time = '(Y-M-D) 0009-04-16 17:28:13'
date: '(Y-M-D) 0009-04-16 17:28:13' = -61874001107 epoch-seconds
date: timezone: TZ="UTC" environment value
date: final: -61874001107.571934909 (epoch-seconds)
date: final: (Y-M-D) 0009-04-16 17:28:13 (UTC)
date: final: (Y-M-D) 0009-04-16 17:28:13 (UTC+00)
9
cerdea@piatam:~/Downloads$ env TZ=blah/blah date --debug +%-Y -d '- 2010 years'
date: parsed relative part: -2010 year(s)
date: input timezone: TZ="blah/blah" environment value
date: using current time as starting value: '17:28:26'
date: using current date as starting value: '(Y-M-D) 2019-04-16'
date: starting date/time: '(Y-M-D) 2019-04-16 17:28:26'
date: warning: when adding relative months/years, it is recommended to specify the 15th of the months
date: after date adjustment (-2010 years, +0 months, +0 days),
date:     new date/time = '(Y-M-D) 0009-04-16 17:28:26'
date: '(Y-M-D) 0009-04-16 17:28:26' = -61874001094 epoch-seconds
date: timezone: TZ="blah/blah" environment value
date: final: -61874001094.525620784 (epoch-seconds)
date: final: (Y-M-D) 0009-04-16 17:28:26 (UTC)
date: final: (Y-M-D) 0009-04-16 17:28:26 (UTC+00)
9
cerdea@piatam:~/Downloads$ env TZ=America/Chicago date --debug +%-Y -d '- 2010 years'
date: parsed relative part: -2010 year(s)
date: input timezone: TZ="America/Chicago" environment value
date: using current time as starting value: '12:28:37'
date: using current date as starting value: '(Y-M-D) 2019-04-16'
date: starting date/time: '(Y-M-D) 2019-04-16 12:28:37'
date: warning: when adding relative months/years, it is recommended to specify the 15th of the months
date: error: adding relative date resulted in an invalid date: '(Y-M-D) 0009-04-16 12:28:37'
date: invalid date ‘- 2010 years’
1 cerdea@piatam:~/Downloads$ 

and, with Assaf's test:

cerdea@piatam:~/Downloads$ env TZ=UTC ./inv-year
time() = 1555435812
localtime() = 2019-04-16 17:30:12
              (mday=16 wday=2, isdst=0)
struct tm (after adjustment) = 0009-04-16 17:30:12
                               (mday=16 wday=2, isdst=0)
mktime() after date adjustment = -61874000988
cerdea@piatam:~/Downloads$ env TZ=blahblah ./inv-year
time() = 1555435821
localtime() = 2019-04-16 17:30:21
              (mday=16 wday=2, isdst=0)
struct tm (after adjustment) = 0009-04-16 17:30:21
                               (mday=16 wday=2, isdst=0)
mktime() after date adjustment = -61874000979
cerdea@piatam:~/Downloads$ env TZ=America/Chicago ./inv-year
time() = 1555435831
localtime() = 2019-04-16 12:30:31
              (mday=16 wday=2, isdst=1)
struct tm (after adjustment) = 0009-04-16 12:30:31
                               (mday=16 wday=2, isdst=1)
inv-year: mktime() failed: Value too large for defined data type