Guess we'll have to take the plunge

Just to check, I ran a version of the program with a revision of ysInRange, the function that actually does the range checking to do some of the alleged improvements mentioned earlier:

numWithin :: Integer -> Integer -> [Integer] -> Int

numWithin m n xs = length (takeWhile (<= n) $ dropWhile (< m) xs)

simpleYsInRange :: Integer -> Integer -> Int -> Int

simpleYsInRange m n digits = numWithin m n (ysByDigits !! (digits - 1))

-- Now for the real thing. As with the palindrome generation, the caller has
-- the number of digits of interest handy, so we take it as a parameter

ysInRange :: Integer -> Integer -> Int -> Int

ysInRange m n digits
    | digits < 8 = simpleYsInRange m n digits
    | mMSDs > 20 = 0
    | mMSDs > 11 = numWithin m n (twoTwos digits)
    | otherwise  = simpleYsInRange m n digits
    where mMSDs = m `div` tenToThe (digits - 2)

The results? Inconclusive; there's no clear difference. It's going to take a better data structure.

UPDATE:  here's the "cost center" listing from profiling output.

COST CENTRE                MODULE  %time %alloc

numWithin                  Main     28.2    6.1
solve                      Main     18.1   30.3
digitsIn.digitsIn'         Main     14.8   16.6
backwards.backwards'       Main     12.1   15.0
backwards.backwards'.(...) Main      9.8   11.4
nDigitYs                   Main      4.4    5.0
choices                    Main      4.3    9.4
tenToThe                   Main      1.5    0.0
floorSqrt.floorSqrt'.y     Main      1.3    1.0
digitsIn                   Main      1.3    0.0
noTwos                     Main      1.0    1.1
oddDigitsPals              Main      0.6    1.6

So it is indeed walking the lists of generated palindromes that's the time sink. (I do wonder about digitsIn and backwards', though; I guess arbitrary precision arithmetic will mean heap allocation, but that much?)