As an experiment, try taking Scalate out of the equation. In theory, you should be able to run a Scalatra REST API and use roughly 64MB in the JVM, if you run without Scalate templating (which you shouldn't need for that sort of application).
It's hard to know definitively without poking at your deployment a bit. But as a guess, the Scalate compiler, which is now bundled by default into Scalatra's default G8 template in order to provide pre-compiled views for extra speed in production, may be putting you over Heroku's limit.
There's probably a way to get template precompilation to work outside of the Heroku deploy process, but I'm not familiar enough with Heroku deployments or Scalate template compilation to know how that'd work. If you deploy using a WAR, the templates will already be precompiled and you don't incur that startup penalty the first time.