**Haskell 2063+2*151=2365**

It's guaranteed the generated regex has length O(log n log log n).
 
`matchIntRange 12345 7654321`

`1(2(3(4(5[6-9]|[6-9]\d)|[5-9]\d\d)|[4-9]\d{3})|[3-9]\d{4})|[2-9]\d{5}|[1-6]\d{6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([012]\d\d|3([01]\d|2[01])))))`

    import Data.Digits
    
    data RegEx = Range Int Int | MatchNone | All Int
                | Or RegEx RegEx | Concat [RegEx] 
    
    alphabet = "\\d"
    
    instance Show RegEx where
      show (Range i j)
       | i == j    = show i
       | i+1 == j  = concat ["[",show i,show j,"]"]
       | i+2 == j  = concat ["[",show i,show (i+1), show (i+2),"]"]
       | otherwise = concat ["[",show i,"-",show j,"]"]
      show (Or a b)  = show a ++ "|" ++ show b
      show MatchNone = "^$"
      show (All n) 
       | n < 3     = concat $ replicate n alphabet
       | otherwise = concat [alphabet,"{",show n,"}"] 
      show e@(Concat xs) 
       | atomic e  = concatMap show xs
       | otherwise = concatMap show' xs
       where show' (Or a b) = "("++show (Or a b)++")"
             show' x = show x
             atomic (Concat xs) = all atomic xs
             atomic (Or _ _)    = False
             atomic _           = True
    
    -- Match integers in a certain range
    matchIntRange :: Int->Int->RegEx
    matchIntRange a b
     | 0 > min a b = error "Negative input"
     | a > b       = MatchNone
     | otherwise = build (d a) (d b)
     where build :: [Int]->[Int]->RegEx
           build [] [] = Concat [] 
           build (a@(x:xs)) (b@(y:ys))
             | sl && x == y       = Concat [Range x x, build xs ys]
             | sl && all9 && all0 = Concat [Range x y, All n]
             | sl && all0         = Or (Concat [Range x (y-1), All n]) upper
             | sl && all9         = Or lower (Concat [Range (x+1) y, All n])
             | sl && x+1 <= y-1   = Or (Or lower middle) upper
             | sl                 = Or lower upper
             | otherwise          = Or (build a (nines la)) (build (1:zeros la) b)
             where (la,lb) = (length a, length b)
                   sl      = la == lb
                   n       = length xs
                   upper   = Concat [Range y y, build (zeros n) ys]
                   lower   = Concat [Range x x, build xs (nines n)]
                   middle  = Concat [Range (x+1) (y-1), All n]
                   all9    = all (==9) ys
                   all0    = all (==0) xs
           zeros n   = replicate n 0
           nines n   = replicate n 9
           d 0 = [0]
           d n = digits 10 n



The code below is a simple version that helps with understanding the algorithm, but it doesn't do any optimization to improve the regex size.

`matchIntRange 123 4321`

    (((1((2((3|[4-8])|9)|[3-8]((0|[1-8])|9))|9((0|[1-8])|9))|[2-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|((1((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|[2-3]((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))))|4((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-2]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|3((0((0|[1-8])|9)|1((0|[1-8])|9))|2(0|1)))))

The regular expression has 680 characters.
Here is the code

    import Data.Digits
    
    data RegEx = Range Int Int | MatchNone | Or RegEx RegEx | Concat [RegEx] 
    
    alphabet = "\\d"
    
    instance Show RegEx where
      show (Range i j)
       | i == j    = show i
       | otherwise = concat ["[",show i,"-",show j,"]"]
      show (Or a b)  = concat ["(",show a,"|",show b,")"]
      show MatchNone = "^$"
      show (Concat xs) = concatMap show xs
    
    matchIntRange :: Int->Int->RegEx
    matchIntRange a b
     | 0 > min a b = error "Negative input"
     | a > b       = MatchNone
     | otherwise = build (d a) (d b)
     where build :: [Int]->[Int]->RegEx
           build [] [] = Concat [] 
           build (a@(x:xs)) (b@(y:ys))
             | sl && x == y     = Concat [Range x x, build xs ys]
             | sl && x+1 <= y-1 = Or (Or lower middle) upper
             | sl               = Or lower upper
             | otherwise        = Or (build a (nines la)) (build (1:zeros la) b)
             where (la,lb) = (length a, length b)
                   sl      = la == lb
                   n       = length xs
                   upper   = Concat [Range y y, build (zeros n) ys]
                   lower   = Concat [Range x x, build xs (nines n)]
                   middle  = Concat [Range (x+1) (y-1), build (zeros n) (nines n)]
           zeros n = replicate n 0
           nines n = replicate n 9
           d 0 = [0]
           d n = digits 10 n