(defun match-destruc (pat seq)
  (cond
    ((null pat) nil)
    ((symbolp pat) `(,pat (if (symbolp ,seq) ,seq (return-from nil nil))))
    ((atom pat)
     (list `(,pat
	     (if (atom ,seq) ,seq (return-from nil nil)))))
    ((eq :type (car pat))
     (list `(,(second pat)
	     (if (and (atom ,seq) (typep ,seq ,(third pat)))
		 ,seq (return-from nil nil)))))
    (t
     (let ((r 
	    (let* ((p (car pat))
		   (var (gensym))
		   (rec (if (null (cdr pat))
			    nil
			    (cons `(,var (if (consp ,seq) (cdr ,seq)
					     (return-from nil nil)))
				  (match-destruc (cdr pat) var)))))
	      (if (atom p)
		  (cons `(,p (if (consp ,seq) (car ,seq)
				 (return-from nil nil))) rec)
		  (if (eq (car p) :type)
		      (cons `(,(second p) 
			      (if (and (consp ,seq) 
				       (typep (car ,seq) ,(third p)))
				  (car ,seq) 
				  (return-from nil nil))) rec)
		      (append (match-destruc 
			       p 
			       `(if (consp ,seq)
				    (car ,seq)
				    (return-from nil nil)))
			      rec))))))
       (if (null (cdr pat))
	   (cons `(,(gensym) ; dummy (should be declared to ignore)
		   (if (not (and (consp ,seq) (null (cdr ,seq))))
		       (return-from nil nil)))
		 r)
	   r)))))

Please note that the complexity of match-destruc is O(n) and the generated code is also O(n)