It seems eminently possible to create a type system which categorises the performance characteristic of types (e.g. "fast/slow for serial access, "fast/slow for random access", "memory efficient/inefficient"). Those traits could be abstract types placed into the hierarchy in such a way that the more concrete types inherited from them. However, the performance of any program using those types would depend upon the way they are actually used/accessed. For the type system to make statements about the program itself, usage of (access to) those types would have itself to be represented as types. This would mean forgoing the use of built-in control structures (e.g. for/while loops) and instead using types which implement them. Hence the hierarchy could have an abstract serial-access type and descendant list-serial-access, tree-serial-access types and so on. Efficiency of usage might then be at least partly expressed by the combination and application of these types to each other.
In a functional language like Haskell - which has almost no control structures anyway - this looks to me fairly practical and enforceable. In Java, however, such a system seems much less achievable (not so much from the implementation as from the enforceability/trustworthiness of the result).
Haskell already allows us to state definitively how much of a program is pure and provides ways of confining particular activities within sealed boxes. Since parallelism/concurrency in Haskell is implemented through the type system, it could be argued that it is already part of the way there (to what you want). In contrast, imperative languages (even statically typed ones like Java) offer the coder many, many ways to subvert any attempt at this.