**Haskell, 1272 chars, reg size 18932 chars** 

This is a simple version. The regular expression size grows exponentially. A longer and less intuitive solution can bring this down to O(log^2 n).

It's easy to see why this is inefficient, it breaks [a-b] into a,[a+1 - b-1],b. Also there are many redundant parentheses.

The code can be made shorter but reg size clearly dominates. 

`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