Here's some more ideas (for either Assembly or Higher-Level language), in no particular order:
Minimize the use of parameters for functions by replacing them with global variables, where possible, and to the extent RAM availability allows. This will reduce the amoung of SP based instructions (that have a one byte penalty each) and cut down the size a bit.
Remove unused code and data (e.g., strings, tables) from libraries.
Replace general purpose routines with shorter more specific ones. For example, if you have a general purpose routine that converts binary to ASCII string but uses 32-bit integers, and you only need support for 8-bit, a lot of code will be removed.
In the same spirit, use variables no bigger than what is actually needed. It's not just the RAM you save but also all the related manipulation code. Possible automatic size or type conversions in various statements should be considered, also, as they too add code.
Search for common statements in different functions and replace them with functions themselves. In higher level languages, it is easy to casually repeat statements because they're easier to write inline than setup a function to do them.
If your original is in Higher-level language and all other advice fails, you can rewrite portions or even the whole thing in assembly for huge savings in program space (1/10th the original size or better is usually feasible).