I have used single-link clustering on 100k objects with ELKI. The SLINK implementation there is reasonably fast - it should complete in 10 minutes or so on this size of data. It doesn't keep a 70000x70000 matrix in memory (SLINK is $O(n^2)$ runtime, $O(2n)$ memory - much better than the naive algorithm which is $O(n^3)$ runtime and $O(n^2)$ memory - but also note that SLINK can only do single-linkage clustering). But categorial variable support isn't available in the download package - you would need to implement the parser, data type and the distance function yourself (which isn't hard, because there is a Tutorial that worked for me).
Or you encode your categories as numbers, and use one of the included distance functions.
There are also various attempts at making an approximative hierarchical clustering in much less time. Wasn't BIRCH an algorithm like this? But I don't know a good implementation of BIRCH.
But have you validated your distance function? If your distance isn't working well, hierarchical clustering (or any clustering based on distance) will fail. I always suggest that people first understand how to quantify similarity. Then cluster.